亚马逊做外贸英文网站百度收录站长工具
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：数学
根据欧几里得-欧拉定理，每个偶完全数都可以写成 2p-1(2p-1) 的形式，其中 p 为为素数且 2p-1 为素数。
由于目前奇完全数还未被发现，因此题目范围 [1, 108] 内的完全数都可以写成上述形式。
这一共有如下 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)。