PerfectNumber [source code]

public class PerfectNumber {
static
/******************************************************************************/
public class Solution {
    public boolean checkPerfectNumber(int num) {
        if (num == 1) return false;
        int sum = 1;
        int lo = 1, hi = Integer.MAX_VALUE;
        while (lo < hi) {
            lo++;
            hi = num / lo;
            if (num % lo == 0) {
                if (lo < hi) {
                    sum += lo + hi;
                } else if (lo == hi) {
                    sum += lo;
                }
            }
        }
        return sum == num;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        PerfectNumber.Solution tester = new PerfectNumber.Solution();
        int[] inputs = {0, 1, 6, 28, 30, 496, 9999_9999};
        for (int i : inputs) System.out.println(i + " -> " + tester.checkPerfectNumber(i));
    }
}

这种 math 题目, 肯定有巧妙的方法的, 这个知道就知道, 不知道也不要强求, 真正碰到这种题目, 最重要的是穷举的暴力做法要想到;
不要认为这个要求很简单, 这个题目的暴力做法非常简单, 但是刚开始看到这个题目的时候还真是有点愣神;

这个题目的暴力解法就很简单:

public class Solution {  
    public boolean checkPerfectNumber(int num) {  
        int sum = 1;  
        for (int i = 2; i <= num / 2; i++) {  
            if (num % i == 0) sum += i;  
        }  
        return sum == num;  
    }  
}

不过这个最后是没有办法通过的, 故意有一个 case 让这个超时了;

注意这个代码, num == 0 Corner Case按理说是要判断一下的, 不过实际上是不用写上去的, 因为如果是0, 反正最后的return test equality其实反正是 false; 而0本身就应该还return false;

why is 1 false?
虽然不知道, 不过无论是OJ 还是 Wiki 都说1不算, 不知道为什么, 我干脆就当一个 special case 给处理了;

最后的速度是14ms (58%), 算是还好;

另外看起来好像内部的那个 if 不需要 ruleout lo > hi的情况, 不过如果 num 是1的话, 正好就能进入这个情况;

这个 while 循环刚开始写的时候也是有点头疼, 因为一开始的想法是 lo 在 declare 的时候初始化为2. 但是后来发现这样写就没有办法做到用 while 的 header 来 terminate 了; 所以直接让 lo 初始化为1. 这个虽然看起来好像没有什么实际的意义, 但是 init 的意义, 主要是让iteration1能够顺利的触发; 把操作全都藏在 body 里面, 这样一般初始化的 value, 可以是, 比如第一个你想处理的 value(这里是2), 朝前 backup 一个操作(这里是++), 也就是 lo 初始化为1了;
不过感觉这个思路还是不够 general, 但是暂时可以这么用;

editorial 的第三个方法的思路还算更加简单, 还是类似用我的第一个版本的穷搜, 但是直接把终点设置到sqrt(n). 这个好像之前做题的时候讨论过了: divisor 的上限就是sqrt(n).

这个是他的代码:

    public boolean checkPerfectNumber(int num) {  
        if (num <= 0) {  
            return false;  
        }  
        int sum = 0;  
        for (int i = 1; i * i <= num; i++) {  
            if (num % i == 0) {  
                sum += i;  
                if (i * i != num) {  
                    sum += num / i;  
                }  

            }  
        }  
        return sum - num == num;  
    }

他同样处理了两个 divisor 相等的情形;

editorial 的最后一个解, 是数学上的一个性质:

Approach #4 Euclid-Euler Theorem [Accepted]

Algorithm

Euclid proved that 2^{p−1}(2^p − 1) is an even perfect number whenever 2^p − 1 is prime, where p is prime.

For example, the first four perfect numbers are generated by the formula 2^{p−1}(2^p − 1), with p a prime number, as follows:
for p = 2: 2^1(2^2 − 1) = 6
for p = 3: 2^2(2^3 − 1) = 28
for p = 5: 2^4(2^5 − 1) = 496
for p = 7: 2^6(2^7 − 1) = 8128.

Prime numbers of the form 2^p − 1 are known as Mersenne primes. For 2^p − 1 to be prime, it is necessary that p itself be prime. However, not all numbers of the form 2^p − 1 with a prime p are prime; for example, 2^{11} − 1 = 2047 = 23 × 89 is not a prime number.

You can see that for small value of p, its related perfect number goes very high. So, we need to evaluate perfect numbers for some primes (2, 3, 5, 7, 13, 17, 19, 31) only, as for bigger prime its perfect number will not fit in 64 bits.

public class Solution {  
    public int pn(int p) {  
        return (1 << (p - 1)) * ((1 << p) - 1);  
    }  
    public boolean checkPerfectNumber(int num) {  
        int[] primes=new int[]{2,3,5,7,13,17,19,31};  
        for (int prime: primes) {  
            if (pn(prime) == num)  
                return true;  
        }  
        return false;  
    }  
}

Problem Description

We define the Perfect Number is a positive integer that is equal to the sum of all its positive divisors except itself.

Now, given an integer n, write a function that returns true when it is a perfect number and false when it is not.
Example:
Input: 28
Output: True
Explanation: 28 = 1 + 2 + 4 + 7 + 14
Note: The input number n will not exceed 100,000,000. (1e8)

Difficulty:Easy
Total Accepted:10.2K
Total Submissions:30.2K
Contributor: wallflower
Companies
fallible
Related Topics
math