507. Perfect Number.md

title	toc	date	tags	top
507. Perfect Number	false	2017-10-30	Leetcode Math	507

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)

分析

完全数的所有的真因子(即除了自身以外的约数)的和，恰好等于它本身。时间复杂度$O(\log n)$。

public boolean checkPerfectNumber(int num) {
    if (num < 2) return false;
    // 1 肯定是因子
    int sum = 1;
    for (int i = 2; i * i < num; i++) { // i从2开始
        if (num % i == 0)
            sum += i + num/i;
    }
    return sum == num; 
}