Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Algorithm to check if a number if a perfect number

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 !

like image 644
codeObserver Avatar asked Jul 04 '11 02:07

codeObserver


People also ask

What is the algorithm for perfect number?

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.

How do you know if 496 is a perfect number?

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.

Why is 4 not 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 .


1 Answers

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

like image 139
Nemo Avatar answered Oct 10 '22 17:10

Nemo