LeetCode 507. 完美数
目录
题目描述
✅ 507. 完美数
题意分析
给一个正整数
num，判断它是不是「完美数」：把它所有小于自身的正因子加起来，和恰好等于它本身。例如28的真因子是1, 2, 4, 7, 14，和为28，所以28是完美数。「小于自身」这四个字是全部题意的重心——
num自己是自己的因子，但不能计入。等价的说法是：把num的全部因子求和后减去num，看是否还等于num；也就是全体因子之和是否等于2 * num。两种口径都对，但必须在代码里从头到尾只用其中一种，混着用必错。约束 $1 \le num \le 10^8$ 给出了明确信号：$O(num)$ 地把
1到num - 1全试一遍是一亿次取模，在判题机上是压线甚至超时的；而这个上界对 $O(\sqrt{num})$（一万次循环）来说宽松得离谱。所以正解应当把枚举范围压到根号级别。压缩的依据来自因子的天然结构：因子总是成对出现的——只要i能整除num，num / i也一定能整除，且这两个数一个不超过 $\sqrt{num}$、另一个不小于 $\sqrt{num}$。枚举小的那一半，大的那一半白送。边界有三处。
num = 1时真因子集合是空集，和为0而不是1，必须返回false；num是完全平方数时（如36的6 × 6），配对的两个因子重合，只能计一次；i * i在i接近 $10^4$ 时不会溢出 32 位，但把循环条件写成i <= num / i或用long相乘更保险。
解法：遍历因子成对求和
核心思路
最朴素的写法是让
i从1跑到num - 1，凡是能整除num的就累加，最后比较总和与num。逻辑上无懈可击，但num上限一亿，这一亿次取模运算是纯粹的浪费——因为真正的因子极其稀疏，一亿个候选里可能只有几十个是因子。瓶颈在于我们把每个因子都独立地找了一遍，完全没有利用因子的结构。关键观察是：因子是成对的。若
num = a * b，那么a和b同时都是因子，而且 $\min(a, b) \le \sqrt{num} \le \max(a, b)$。这意味着每一对因子里，小的那个一定落在 $[1, \sqrt{num}]$ 区间内。于是只要把i扫到 $\sqrt{num}$ 为止，就能一个不漏地枚举出所有因子对，把大的那半通过num / i直接算出来，枚举量从 $10^8$ 降到 $10^4$。接着处理「真因子」这个限制。
1永远是因子，与它配对的是num自己，而num不能计入。与其在循环里做特判，不如把这一对拆开手工处理：直接令累加器初值为1（把小的那个计入），永不加入num（把大的那个排除）。这样循环就可以从i = 2开始，循环体内不需要任何「是不是num自己」的判断。同时这个初值天然让num = 1的情况出错——1的真因子和应为0却被算成了1——所以必须在最前面用num <= 1提前返回false。最后是完全平方数。当
i * i == num时，i与num / i是同一个数，两次累加会把它算重。加一个other != i的判断即可。循环不变量：每轮循环开始前，
sum等于「num的全部真因子中，那些小于当前i的因子，以及它们各自配对的大因子」之和。循环结束时i已越过 $\sqrt{num}$，所有因子对都被处理过，sum就是完整的真因子和。
解题步骤
- 先判
num <= 1直接返回false。为什么：1的真因子集合为空、和为0，而主逻辑把sum初始化成1，会误判1为完美数；同时题目保证num为正，把非法与最小规模一起挡在门外，主循环就不必再操心。- 令
sum = 1。为什么：这一步等价于「先把因子对(1, num)手工拆开」——小因子1计入，大因子num是它自己，按定义排除。有了这个初值，后面的循环体里不再需要任何排除自身的判断。- 让
i从2开始循环，条件写成i <= num / i。它等价于 $i^2 \le num$，覆盖每对因子中较小的一方，同时从表达式上避免乘法溢出。- 若
num % i == 0，先sum += i。i从 2 起且不超过平方根，因此一定小于num，属于真因子。- 再取
other = num / i，仅当other != i时sum += other。为什么：other是与i配对的大因子，因为i >= 2所以other <= num / 2 < num，同样是真因子、同样该计入；而当num是完全平方数且i恰为其平方根时两者相等，加两次就重复了。- 返回
sum == num。为什么：题目要的就是真因子和与自身相等这个布尔判定，不需要额外的标志位。以
num = 28走一遍：28 > 1，通过前置判断。sum = 1（对应因子对(1, 28)中取1）。
i = 2：4 <= 28，28 % 2 == 0，sum = 1 + 2 = 3；other = 14，与i不等，sum = 3 + 14 = 17。
i = 3：9 <= 28，28 % 3 == 1，不是因子，跳过。
i = 4：16 <= 28，28 % 4 == 0，sum = 17 + 4 = 21；other = 7，不等，sum = 21 + 7 = 28。
i = 5：25 <= 28，28 % 5 == 3，跳过。
i = 6：36 > 28，循环结束。返回28 == 28为true。注意
7和14这两个大因子从未被i直接枚举到，它们是在i = 4和i = 2时以num / i的身份被捎带算进来的——这正是把枚举量砍到根号级别的原因。再看一个完全平方的例子num = 36：i = 6时36 % 6 == 0，sum += 6，随后other = 6与i相等，被other != i拦下，只算了一次；最终sum = 1 + 2 + 18 + 3 + 12 + 4 + 9 + 6 = 55 != 36，返回false。
代码实现
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})$。凭什么：循环变量
i从2递增到 $\sqrt{num}$ 为止，共约 $\sqrt{num}$ 轮，每轮只有一次取模、一次除法和常数次加法与比较；num上限 $10^8$ 时循环体最多执行一万次。- 空间复杂度：$O(1)$。凭什么：只用了
sum、i、other三个整型变量，没有开数组、没有递归，占用与num的大小无关。
关键点总结
- 「因子成对出现，小的那个必然不超过 $\sqrt{n}$」是所有因子枚举题的通用降维手段，能把 $O(n)$ 变成 $O(\sqrt{n})$。面试中被问到求因子、求约数个数、判质数时，这句话应该脱口而出。
- 把一个特殊的因子对（这里是
(1, num)）提到循环外手工处理，可以让循环体保持无分支的干净形态。用初值编码边界，比在循环里加判断更不容易写错。- 完全平方数导致配对重合，是「成对枚举」这一手法的固定副作用，写下
num / i的同时就该条件反射地补上去重判断。- 「真因子」与「全部因子」是两套口径，差一个
num本身。先在纸上把口径钉死再动手，可以避免绝大多数偏差。- 循环条件写
i * i <= num时要留意乘法溢出；用i <= num / i改写既避免溢出又不需要类型转换，是更稳的写法。- 面试延伸：完美数在 $10^8$ 内其实只有
6, 28, 496, 8128, 33550336五个，因此打表也能过。但直接答打表会被认为回避了考点，正确的做法是先讲清 $O(\sqrt{n})$ 枚举，再把打表作为「已知数据范围极小时的工程优化」补充说明。
易错点总结
- 忘记
num <= 1的前置判断：num = 1→sum保持初值1，返回1 == 1为true，但1没有真因子，正确答案是false。sum初值写成0：num = 28→ 因子1从未被累加（循环从2开始），最终sum = 27，返回false。sum初值写成1却让循环也从i = 1开始：num = 28→i = 1时又加了一次1，还把other = 28也加进去，sum = 56，彻底跑偏。- 漏掉
other != i的去重：num = 36时平方根 6 会被加入两次，算出 61 而不是真因子和 55。即使该例最终仍为false，因子和已经失真。- 上界写成
i <= num / 2：num = 99999999→ 循环执行约五千万次，虽然结果正确，但白白慢了三个数量级，在更严格的时限下超时。- 上界写成
i < num且不做成对累加：num = 10^8→ 一亿次取模，直接超时。- 把
num自身也加进sum：num = 28→sum = 56，返回false；若同时把判定改成sum == 2 * num才对，但两种口径混用必错。- 循环条件写
i * i <= num且不考虑位宽：当前上界下碰巧安全，但扩展到完整 32 位输入会溢出；i <= num / i从表达式上消除了风险。other写成num / i后又误加了i：即在if (other != i)分支里写sum += i→ 小因子被加两次，num = 28得sum = 34，判定失败。- 用
num % i == 0判定后直接return：把「找到一个因子」当成了终止条件 → 只累加了最小因子就返回，任何合数都被判成false。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 204. 计数质数 | 中等 | 要一次性判定 [2, n) 全体的整除性，逐个开根号会超时，须用筛法 |
| 367. 有效的完全平方数 | 简单 | 只关心 $\sqrt{n}$ 是否为整数，可用二分或牛顿迭代做到 $O(\log n)$ |
| 633. 平方数之和 | 中等 | 同样是找一对数相配，但配对关系是加法而非乘法，用双指针从两端夹逼 |
| 728. 自除数 | 简单 | 拆的是十进制数位而不是因子，判断的是数被自己每一位整除 |
| 172. 阶乘后的零 | 中等 | 统计的是质因子 5 的总个数，靠不断除以 5 累计而非枚举因子 |
| 263. 丑数 | 简单 | 只需反复除尽 2, 3, 5 三个指定质因子，不必枚举全部因子 |
| 69. x 的平方根 | 简单 | 求的是根号本身而非用它做上界，考点在二分的下取整与溢出处理 |
| 1071. 字符串的最大公因子 | 简单 | 把整除关系搬到字符串长度上，答案由 gcd 决定而非逐个试除 |