Algorithm to check if a number if a perfect number

Question

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 :

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

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 !

Answer 1

#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;
}

Answer 2

Edit: Dang, I failed the interview! :-(
In my over zealous attempt at finding tricks or heuristics to improve upon the "factorize + enumerate divisors + sum them" approach, I failed to note that being 1 modulo 9 was merely a necessary, and certainly not a sufficient condition for at number (other than 6) to be perfect...
Duh... with on average 1 in 9 even number satisfying this condition, my algorithm would sure find a few too many perfect numbers ;-).
To redeem myself, persist and maintain the suggestion of using the digital root, but only as a filter, to avoid the more expensive computation of the factor, in most cases.

---

[Original 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 suggesting the digital root trick for even numbers is that this can be computed without the help of an arbitrary length arithmetic library (like GMP). It is also much less computationally expensive than the decomposition in prime factors and/or the factorization (2^(p-1) * ((2^p)-1)).   Therefore if the interviewer were to be satisfied with a "No perfect" response for odd numbers, the solution would be both very efficient and codable 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

---

On this relatively odd interview question...
I second andrewdski's comment to another response in this post, that this particular question is rather odd in the context of an interview for a general purpose developer.
As with many interview questions, it can be that the interviewer isn't seeking a particular solution, but rather is providing an opportunity for the candidate to demonstrate his/her ability to articulate the general pros and cons of various approaches. Also, if the candidate is offered an opportunity to look-up generic resources such as MathWorld or Wikipedia prior to responding, this may also be a good test of his/her ability to quickly make sense of the info offered there.

Answer 3

Here's a quick algorithm just for fun, in PHP - using just a simple for loop. You can easliy port that to 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\'s perfect!' : 'Not a perfect number.';
    }

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

Answer 4

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...)