I am looking for an algorithm to find if a given number is a perfect number.
The most simple that comes to my mind is :
Is there a better way to do this ?. On searching, some Euclids work came up, but didnt find any good algorithm. Also this golfscript wasnt helpful: https://stackoverflow.com/questions/3472534/checking-whether-a-number-is-mathematically-a-perfect-number .
The numbers etc can be cached etc in real world usage [which I dont know where perfect nos are used :)]
However, since this is being asked in interviews, I am assuming there should be a "derivable" way of optimizing it.
Thanks !
If the input is even, see if it is of the form 2^(p-1)*(2^p-1)
, with p
and 2^p-1
prime.
If the input is odd, return "false". :-)
See the Wikipedia page for details.
(Actually, since there are only 47 perfect numbers with fewer than 25 million digits, you might start with a simple table of those. Ask the interviewer if you can assume you are using 64-bit numbers, for instance...)