Problem

Given an integer n, return true if n is a perfect number, otherwise return false.

Definition

A perfect number is a natural number that is equal to the sum of its positive divisors, excluding the number itself. A divisor of an integer x is an integer that can divide x evenly.

The first perfect numbers are 6, 28, 496, 8128 and all of them are in form $$ 2^{n-1}.(2^n - 1)$$

1
2
3
4

6 = 3 + 2 + 1
28 = 14 + 7 + 4 + 2 + 1
496 = 248 + 124 + 62 + 31 + 16 + 8 + 4 + 2 + 1
8128 = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 127 + 254 + 508 + 1016 + 2032 + 4064

Greek mathematician Euclid proved that the formula is en even perfect number whenever $$ 2^{p-1} $$ is a prime.

So far only even perfect numbers have been discovered, but the existence of odd perfect numbers was never disproved. According to the current state of knowledge, the odd perfect number must be higher than $$ 10^{300} $$.

Examples

Example 1:

1
2
3
4
5
6

Input:
num = 28
Output:
 true
Explanation: 28 = 1 + 2 + 4 + 7 + 14
1, 2, 4, 7, and 14 are all divisors of 28.

Example 2:

1
2
3
4

Input:
num = 7
Output:
 false

Solution

Method 1 - Loop

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

public boolean checkPerfectNumber(int num) {
    //odd perfect number (probably) does not exist, and even if it does, it has a higher value than long can represent
    if (num % 2 == 1) {
        return false;
    }

    long sum = 1; //1 is a trivial divisor
    long i = 2;
    while (i * i <= num) { //until i <= sqrt(number)
        if (num % i == 0) {
            sum += i;
            sum += num / i;
        }
        i++;
    }
    if (i * i == num) { //perfect square, sqrt(number) was added twice
        sum -= i;
    }
    return sum == num;	
}