Perfect numbers

Posted on

Question :

algoritmo "numeros_perfeitos"
c, n:inteiro
nv, np, npv:real
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
  se np = n entao
  np <- 0
  nv <- 0

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?


Answer :

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.

Leave a Reply

Your email address will not be published. Required fields are marked *