题目描述

对于一个 正整数，如果它和除了它自身以外的所有正因子之和相等，我们称它为“完美数”。

给定一个 正整数 n， 如果他是完美数，返回 True，否则返回 False。

样例

输入: 28
输出: True
解释: 28 = 1 + 2 + 4 + 7 + 14

注意

• 输入的数字 n 不会超过 100,000,000 (1e8)。

算法

(枚举) $O(\sqrt n)$

1. 从 $i = 2$ 开始，逐一枚举 n 的正因数，直到 $\sqrt n$ 为止。若 $n\%i=0$，则找到了一个正因子；同时，若 $i * i \neq n$，则另外找到了 $\frac{n}{i}$ 为正因子。最后求和时需要统计上正因子 1。
2. 注意 n 为 1 的特殊情况。

时间复杂度

• 最多枚举 $O(\sqrt n)$ 个数字，故时间复杂度为 $O(\sqrt n)$。

C++ 代码

class Solution {
public:
    bool checkPerfectNumber(int num) {
        if (num == 1)
            return false;

        int tot = 0;
        for (int i = 2; i * i <= num; i++)
            if (num % i == 0) {
                tot += i;
                if (i * i != num)
                    tot += num / i;
            }

        return tot + 1 == num;
    }
};