【LeetCode每日一题】507. 完美数【简单】

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

给定一个 整数 n， 如果是完美数，返回 true，否则返回 false

示例 1：

输入：num = 28 输出：true 解释：28 = 1 + 2 + 4 + 7 + 14 1, 2, 4, 7, 和 14 是 28 的所有正因子。 示例 2：

输入：num = 6 输出：true 示例 3：

输入：num = 496 输出：true 示例 4：

输入：num = 8128 输出：true 示例 5：

输入：num = 2 输出：false  

提示：

1 <= num <= 108

题解： 自己写的有点挫，复杂度是O(num)的，但是实际上是可以将复杂度降到O(根号num)的。

//自己写的，很直接，但是复杂度高
class Solution {
public:
    bool checkPerfectNumber(int num) {
        int ans = 0;
        for(int i = 1; i <= num / 2; i++){
            if(num % i == 0) {
                ans += i;
                //cout<<i<<endl;
            }
        }
        if(ans == num) return true;
        else return false;
    }
};

//官方题解。
class Solution {
public:
    bool checkPerfectNumber(int num) {
        if (num == 1) {
            return false;
        }

        int sum = 1;
        for (int d = 2; d * d <= num; ++d) {
            if (num % d == 0) {
                sum += d;
                if (d * d < num) {
                    sum += num / d;
                }
            }
        }
        return sum == num;
    }
};

官方题解还提供了一个更加直接的大表方法，看上去只有5个数是满足这个情况的。

class Solution {
public:
    bool checkPerfectNumber(int num) {
        return num == 6 || num == 28 || num == 496 || num == 8128 || num == 33550336;
    }
};

复杂度分析

时间复杂度：O(1)。 空间复杂度：O(1)。