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 !
A number is a perfect number if is equal to sum of its proper divisors, that is, sum of its positive divisors excluding the number itself. Write a function to check if a given number is perfect or not. Examples: Input: n = 15 Output: false Divisors of 15 are 1, 3 and 5.
Now, the sum of divisors of a number, excluding the number itself, is called its aliquot sum, so we can define a perfect number as one that is equal to its aliquot sum. Hence, the sum of these factors is equal to the given number. So, 496 is a perfect number.
4 is not a perfect number because the sum of its factors (besides 4 itself), 1+2, is less than 4. Numbers like 4 are known as deficient numbers .
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...)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With