Perfect numbers

Question

Perfect numbers

algoritmo "numeros_perfeitos"
var
c, n:inteiro
nv, np, npv:real
inicio
para n <- 1 ate 100 faca
  para c <- 1 ate n faca
     se n % c = 0 entao
        nv <- n / c
        se nv < n entao
           np <- nv + np
        fimse
     fimse
  fimpara
  se np = n entao
     escreva(np)
  fimse
  np <- 0
  nv <- 0
fimpara
fimalgoritmo

I wrote this code for this exercise:

Write an algorithm that generates and writes the first 4 numbers perfect. A perfect number is one that is equal to the sum of its splitter. Ex.: 6 = 1+2+3; 28= 1+2+4+7+14.

But it hangs how much I put from n to 10000 did I do something wrong? And why does it run many cycles in the internal structure(I think it's 100000 cycles)? Was my logic bad?

3

for algoritmo loop visualg

Author: Zulian, 2017-10-03

Source

1 answers

score 3 · Accepted Answer

Is probably taking time to execute, as it will execute summation of 1 - > n. that is, for a case where N = 10000, it executes 50005000 times that cycle of yours. Then it hangs, exactly, for taking to perform this amount of loops. Some ways you can improve this algorithm are:

Whenever you find the perfect fourth Number, stop the loop execution: do a check if 4 numbers were found, if yes, use the command break in the outermost loop
You don't need to run the innermost loop from 1 to n, but from 2 to N^1/2: first that 1 will always divide a number, so instead of starting its sum with 0, you can start with 1. Second that multiplication is a complementary operation, so if you know one of the factors, you will know both (in case of multiplication of only 2 terms), this means that you do not need to find out all the divisors of N, but only half from them, for this you take the square root of this number. Done that, you have to add the two factors to your account, adding C and N / C, when N % C = 0.