LeetCode 507. 完美数
题目描述
✅ 507. 完美数
题意分析
判断正整数
num是否等于所有真因子之和。真因子是能整除num且小于它的正整数，所以必须排除num自身。对num>1，因子1要计入；1自己没有真因子，因此不是完美数。
解法：遍历因子成对求和
核心思路
[!blue]
若
i能整除num，另一个因子就是num/i。一对因子的乘积为num，至少有一个不超过平方根，所以只枚举较小者，就能找到全部因子对，无需一直扫描到num-1。先把因子对
(1,num)单独处理：总和初始化为1，不加入num，循环从2开始。之后找到的因子对，两项都小于num，可以计入真因子和；若两项相等，说明它们都是平方根，只能加一次。枚举条件写成
i <= num/i，对正整数等价于i*i <= num，同时避免先做平方乘法。每个非平方因子对只会由它的较小成员触发，平方因子又做了去重，因此循环结束时，总和既没有遗漏也没有重复，直接与num比较即可。
解题步骤
- 一的真因子和为零，直接返回假。
- 总和从一开始，枚举满足
i<=num/i的小因子。- 整除时加入 i 与不同的配对因子。
- 比较总和与原数。
质数不会找到额外因子，最终总和保持为
1；完全平方数必须包含平方根这一项，因此循环上界要取等号。
代码实现
class Solution {
public boolean checkPerfectNumber(int num) {
// 1 的真因子和为 0，而下面 sum 初值为 1，必须提前挡掉。
if (num <= 1) {
return false;
}
// 初值 1 相当于手工拆开因子对 (1, num)：计入 1，排除 num 自身。
int sum = 1;
for (int i = 2; i <= num / i; i++) {
if (num % i == 0) {
sum += i;
int other = num / i;
// num 是完全平方数时 other 与 i 重合，只能算一次。
if (other != i) {
sum += other;
}
}
}
return sum == num;
}
}
func checkPerfectNumber(num int) bool {
// 1 的真因子和为 0，而下面 sum 初值为 1，必须提前挡掉。
if num <= 1 {
return false
}
// 初值 1 相当于手工拆开因子对 (1, num)：计入 1，排除 num 自身。
sum := 1
for i := 2; i <= num/i; i++ {
if num%i == 0 {
sum += i
other := num / i
// num 是完全平方数时 other 与 i 重合，只能算一次。
if other != i {
sum += other
}
}
}
return sum == num
}
复杂度分析
- 时间复杂度：$O(\sqrt{num})$，每对因子只枚举较小者。
- 空间复杂度：$O(1)$，只保存计数与配对值。
关键点总结
[!green]
- 每个因子都有配对值，只需枚举到平方根便能覆盖全部因子。
- 单独处理
(1,num)排除自身，判断两因子是否相等消除平方根重复。
易错点总结
[!yellow]
- 把自身加入总和，却仍与原数比较，混淆了真因子口径。
- 平方根加两次，会错误扩大因子和。
- 总和从零开始却仍从二枚举，会漏掉因子一。
- 扩大枚举到半数却仍按因子对累加，会重复计算已经处理的因子对。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1390. 四因数 | 中等 | 同样成对枚举因子并累加因子和，原题还限制恰有四个因子，本题比较真因子和与原数。 |
| 319. 灯泡开关 | 中等 | 同样利用因子配对，完全平方数的平方根只计一次，原题据此判断因子个数奇偶。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！