Leetcode507. 完美数

Every day a leetcode

题目来源：507. 完美数

解法1：枚举

我们可以枚举 num 的所有真因子，累加所有真因子之和，记作 sum。若 sum=num 则返回 true，否则返回 false。

枚举范围从 [1, sum) 的话，会超时：

枚举范围从 [1, sqrt(sum)]，再让 sum 加上num / i 即可。

注意 i=1 时，不能让sum加上num。

特判 num=1 的情况，返回false。

代码：

/** @lc app=leetcode.cn id=507 lang=cpp** [507] 完美数*/// @lc code=start
// class Solution
// {
// public:
//     bool checkPerfectNumber(int num)
//     {
//         int sum = 0;
//         for (int i = 1; i < num; i++)
//             if (num % i == 0)
//                 sum += i;
//         return sum == num;
//     }
// };
class Solution
{
public:bool checkPerfectNumber(int num){if (num == 1)return false;int sum = 0;for (int i = 1; i <= sqrt(num); i++){if (num % i == 0){sum += i;if (i * i < num && i != 1)sum += num / i;}}return sum == num;}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(sqrt(num))。

空间复杂度：O(1)。

解法2：数学

根据欧几里得-欧拉定理，每个偶完全数都可以写成 2^p-1(2^p-1) 的形式，其中 p 为为素数且 2^p-1 为素数。

由于目前奇完全数还未被发现，因此题目范围 [1, 10⁸] 内的完全数都可以写成上述形式。

这一共有如下 5 个：6, 28, 496, 8128, 33550336。

代码：

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

结果：

复杂度分析：

时间复杂度：O(1)。

空间复杂度：O(1)。