507. 完美数
507. 完美数
题目
A perfect number is a positive integer that is equal to the sum of its positive divisors , excluding the number itself. A divisor of an integer x
is an integer that can divide x
evenly.
Given an integer n
, return true
ifn
is a perfect number, otherwise returnfalse
.
Example 1:
Input: num = 28
Output: true
Explanation: 28 = 1 + 2 + 4 + 7 + 14
1, 2, 4, 7, and 14 are all divisors of 28.
Example 2:
Input: num = 7
Output: false
Constraints:
1 <= num <= 10^8
题目大意
对于一个 正整数 ,如果它和除了它自身以外的所有 正因子 之和相等,我们称它为 「完美数」 。
给定一个 **整数 **n
, 如果是完美数,返回 true
;否则返回 false
。
示例 1:
输入: num = 28
输出: true
解释: 28 = 1 + 2 + 4 + 7 + 14
1, 2, 4, 7, 和 14 是 28 的所有正因子。
示例 2:
输入: num = 7
输出: false
提示:
1 <= num <= 10^8
解题思路
对于一个数 num
,可以从 1 开始枚举其所有可能的正因子,累加这些因子的和,如果 sum == num
,则 num
是完美数。
- 如果
num <= 1
,直接返回false
,因为完美数定义中要求「正因子之和不包括自身」。 - 初始化累加因子的和
sum = 1
,因为 1 是任何数的正因子。 - 枚举所有可能的因子:
- 如果一个数可以被
i
整除,则num / i
也是一个因子。 - 因此,遍历时只需从 2 遍历到
sqrt(num)
,因为超出sqrt(num)
的部分可以通过num / i
推出。 - 将
i
和num / i
加入累加因子和sum
中,注意要避免重复累加平方根的因子。- 例如,49 的平方根是 7,
7 * 7 = 49
,因子 7 只计算一次。
- 例如,49 的平方根是 7,
- 如果一个数可以被
- 遍历结束后,将正因子之和与
num
比较。如果相等,返回true
;否则返回false
。
复杂度分析
- 时间复杂度:
O(sqrt(num))
,遍历范围是从 2 到sqrt(num)
。 - 空间复杂度:
O(1)
,只使用了固定数量的变量存储中间结果。
代码
/**
* @param (number} num
* @return {boolean}
*/
var checkPerfectNumber = function (num) {
if (num <= 1) return false; // 边界情况,1 不是完美数
let sum = 1; // 因为 1 是任何数的正因子
for (let i = 2; i * i <= num; i++) {
if (num % i === 0) {
sum += i; // 累加较小的因子
if (i !== num / i) {
sum += num / i; // 累加较大的因子
}
}
}
// 比较累加因子和 sum 与 num
return sum === num;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
728 | 自除数 | [✓] | 数学 | 🟢 | 🀄️ 🔗 |