完全数是等于其所有真因子(即小于自身的正因数)之和的正整数;不能只试到n/2是因为真因子成对出现且较小因子≤√n,遍历至√n再补配对因子更高效。

什么是完全数,以及为什么不能只试到 n/2
完全数是指一个正整数等于它所有**真因子**(即小于它自身的正因数)之和。比如 6:真因子是 1、2、3,加起来正好是 6。
很多人直觉上会从 1 试到 n/2,这没错但低效——尤其对大数(比如接近 INT_MAX 的数),循环上亿次不现实。关键点在于:真因子成对出现,且其中较小的那个 ≤ √n。所以只需遍历到 sqrt(n),再把配对的因子一并加上。
注意:1 没有真因子(空集和为 0),所以直接返回 false;2 的真因子只有 1,和为 1 ≠ 2,也不是完全数。
如何正确累加真因子(含边界和重复处理)
遍历 i 从 2 到 sqrt(n),跳过 1(单独加),同时避免把 sqrt(n) 算两次。
- 初始化
sum = 1(因为1总是真因子,除非n == 1) - 对每个能整除
n的i:- 加
i - 如果
i != n / i且n / i (保证是真因子),再加 <code>n / i
- 加
- 特别检查
i == 1已处理,i == n不考虑(不是真因子)
示例:n = 28,sqrt(28) ≈ 5,遍历时 i = 2 → 加 2 和 14;i = 4 → 加 4 和 7;最终 1 + 2 + 4 + 7 + 14 = 28。
C++ 实现时的整型溢出与性能陷阱
int 类型在累加因子时可能溢出——比如测试 8128(第四个完全数),其真因子和就是 8128,但中间过程最大加数是 4064,仍在 int 范围内;但若扩展到更大数(如用 long long 测试疑似完全数),sum 必须用更大类型,否则比较 sum == n 会出错。
另一个坑:sqrt(n) 用 int(sqrt(n)) 有精度丢失风险,推荐用 i * i 替代:
int sum = 1; for (int i = 2; i * i <p>这样既避免浮点误差,又不用引入 <code><cmath></cmath></code>。</p><h3>哪些数值得测,哪些可以直接排除</h3><p>完全数极其稀疏:目前已知的所有偶完全数都形如 <code>2^(p−1) × (2^p − 1)</code>,其中 <code>2^p − 1</code> 是梅森素数。这意味着: </p>
- 所有已知完全数都是偶数,奇完全数是否存在仍是未解问题(目前没找到,也没证伪)
- 因此实际判断中,若
n是奇数且 > 1,可快速返回false(虽然不数学严谨,但对现有全部已知情况成立) - 常见测试用例:
6、28、496、8128→ 都应返回true;12、18、100→false
真正容易被忽略的是:函数必须明确处理 n ,否则 <code>sqrt(n) 或循环条件可能行为异常,或导致 sum 初始值逻辑错乱。
C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!











