网站建设维护文档,界面网页设计培训,360建筑网证书,中国摄影师个人网站设计Every day a leetcode
题目来源#xff1a;507. 完美数
解法1#xff1a;枚举
我们可以枚举 num 的所有真因子#xff0c;累加所有真因子之和#xff0c;记作 sum。若 sumnum 则返回 true#xff0c;否则返回 false。
枚举范围从 [1, sum) 的话#xff0c;会超时507. 完美数
解法1枚举
我们可以枚举 num 的所有真因子累加所有真因子之和记作 sum。若 sumnum 则返回 true否则返回 false。
枚举范围从 [1, sum) 的话会超时 枚举范围从 [1, sqrt(sum)]再让 sum 加上num / i 即可。
注意 i1 时不能让sum加上num。
特判 num1 的情况返回false。
代码
/** lc appleetcode.cn id507 langcpp** [507] 完美数*/// lc codestart
// 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 codeend
结果 复杂度分析
时间复杂度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)。
