Algorithm for checking the number if the perfect number

Question

I am looking for an algorithm to find if a given number is an ideal number.

The simplest thing that comes to my mind:

• Find all the factors of the number
• Get the main factors [except for the number itself, if it is prime] and add them to check if it is a perfect number.

Is there a better way to do this? When searching, some Euclidean works came up, but did not find a good algorithm. Also this golfscript didn't help: https://stackoverflow.com/questions/3472534/checking-whether-a-number-is-mathematically-a-perfect-number .

Numbers, etc. can be cached etc. in the real world [that I don’t know where perfect ns are used :)]
However, since this is asked in an interview, I suggest that there should be a “deduction” way to optimize it.

Thanks!

Answer 1

If the input is even, see if it has 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 more details.

(Actually, since there are only 47 perfect numbers with less than 25 million characters, you can start with a simple table. Ask the interviewer if you can assume that you are using 64-bit numbers, for example ...)

Answer 2

Here's a quick algorithm just for fun, in PHP - with a simple for loop. You can easliy port that in other languages:

 function isPerfectNumber($num) { $out = false; if($num%2 == 0) { $divisors = array(1); for($i=2; $i<$num; $i++) { if($num%$i == 0) $divisors[] = $i; } if(array_sum($divisors) == $num) $out = true; } return $out ? 'It\ perfect!' : 'Not a perfect number.'; } 

Hope this helps, not sure if this is what you are looking for.

Answer 3

Edit : Dang, I failed the interview! :-( In my zealous attempt to find tricks or heuristics in order to improve "factorization decomposition + list divisors + sum them", I did not notice that being 1 modulo 9 was simply necessary and, of course, not a sufficient condition for a number (other than 6) to be perfect ...
Duh ... on average, for 1 out of 9 even numbers that satisfy this condition, my algorithm will probably find a few too many perfect numbers ;-).
To redeem yourself, save and support the proposal to use the digital root, but only as a filter to avoid a more expensive factor calculation in most cases.

---

[Initial Attempt: Hall of Shame]

 If the number is even,<br> compute its [digital root][1]. if the digital root is 1, the number is perfect, otherwise it isn't. If the number is odd... there are no shortcuts, other than... "Not perfect" if the number is smaller than 10^300 For bigger values, one would then need to run the algorithm described in the question, possibly with a few twists typically driven by heuristics that prove that the sum of divisors will be lacking when the number doesn't have some of the low prime factors. 

My reason for offering a digital root trick for even numbers is that this one can be computed without using an arbitrary arithmetic length library (like GMP). It is also much less computationally expensive than factorization and / or factorization (2 ^ (p-1) * ((2 ^ p) -1)). Therefore, if the interviewer should be satisfied with a "perfect" answer to odd numbers, the solution will be very effective and compatible in most computer languages.

---

[Second and third attempt ...]

 If the number is even,<br> if it is 6 The number is PERFECT otherwise compute its [digital root][1]. if the digital root is _not_ 1 The number is NOT PERFECT else ..., Compute the prime factors Enumerate the divisors, sum them if the sum of these divisor equals the 2 * the number it is PERFECT else it is NOT PERFECT If the number is odd... same as previously 

---

About this relatively odd interview question ...
Andrewdski's second comment on another answer in this post is that this particular question is rather strange in the context of an interview for a general-purpose developer. As in many questions of the interview, perhaps the interviewer is not looking, but rather gives the candidate the opportunity to demonstrate his ability to formulate common advantages and disadvantages of various approaches. In addition, if the candidate is offered the opportunity to search for common resources, such as MathWorld or Wikipedia, before answering, this can also be a good test of his ability to quickly comprehend the information offered there.

Answer 4

 #include<stdio.h> #include<stdlib.h> int sumOfFactors(int ); int main(){ int x, start, end; printf("Enter start of the range:\n"); scanf("%d", &start); printf("Enter end of the range:\n"); scanf("%d", &end); for(x = start;x <= end;x++){ if(x == sumOfFactors(x)){ printf("The numbers %d is a perfect number\n", x); } } return 0; } int sumOfFactors(int x){ int sum = 1, i, j; for(j=2;j <= x/2;j++){ if(x % j == 0) sum += j; } return sum; }