Perfect numbers

3
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 your   dividers. Ex: 6 = 1 + 2 + 3; 28 = 1 + 2 + 4 + 7 + 14.

But does it lock how much I put from n to 10,000 I did something wrong? And why does it run many cycles in the internal structure (think they are 100000 cycles)? My logic was bad?

    
asked by anonymous 03.10.2017 / 15:19

1 answer

3

It is probably taking a while to execute, as it will perform summation of 1 - > n. That is, for a case where N = 10000, it runs 50005000 times that your cycle. Then it crashes, exactly, by delaying to execute that amount of loops. Some ways you can improve this algorithm are:

  • Whenever you find the perfect room number, stop looping: check if 4 numbers were found, if so, use command interrupt in the outer loop

  • You do not need to run the inner loop from 1 to n, but from 2 to n ^ 1/2: First that 1 will always divide a number, then, 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 the two (in case of multiplication of only 2 terms), this means that you do not need to find ALL the divisors of N, but only HALF of them, for that, you take the square root of that number. If you do this, you have to add the two factors to your account, adding C and N / C, when N% C = 0.

03.10.2017 / 16:36