C++完全数查找算法实现及优化解析

好的，这道题要求找出2到n之间的所有完全数。我们可以先分析一下完全数的定义和判定方法，然后给出C++的实现。 --- ## 🔍 完全数判定思路 一个数 `x` 是完全数，当且仅当**它的所有真因子（除了自身）之和等于它本身**。 例如： - `6` 的真因子是 `1, 2, 3`，和为 `6`。 - `28` 的真因子是 `1, 2, 4, 7, 14`，和为 `28`。 **判断方法：** 遍历从 `1` 到 `x/2`（或者 `sqrt(x)` 优化）找出所有因子并求和，然后比较是否等于 `x`。 --- ## ⚙️ 实现思路（两种常见方案） | 方案 | 复杂度 | 适用场景 | |------|--------|----------| | 简单遍历因子（1 ~ x/2） | O(n²) | 小范围（如 n ≤ 10000） | | 使用 sqrt 优化因子求和 | O(n√n) | 更大范围（如 n ≤ 10^6） | 由于题目未明确 n 大小，这里我给出 **sqrt 优化版本**，既高效又易懂。 --- ## 💻 C++ 代码实现 ```cpp #include <iostream> #include <cmath> using namespace std; // 判断一个数是否是完全数 bool isPerfect(int x) { if (x <= 1) return false; // 1不是完全数 int sum = 1; // 1 总是真因子 int sqrtX = (int)sqrt(x); // 从2到sqrt(x)找因子 for (int i = 2; i <= sqrtX; i++) { if (x % i == 0) { sum += i; if (i != x / i) { // 避免重复加平方根 sum += x / i; } } } return sum == x; } int main() { int n; cin >> n; for (int i = 2; i <= n; i++) { if (isPerfect(i)) { cout << i << endl; } } return 0; } ``` --- ## 🧩 代码解释 - **isPerfect函数**： - 先判断 `x <= 1` 直接返回 false（因为1不算完全数）。 - 初始化 `sum = 1`，因为任何大于1的数的真因子都包含1。 - 从 `2` 到 `sqrt(x)` 遍历，找到一对因子 `i` 和 `x/i`。 - 如果 `i == x/i`（即平方根），只加一次。 - 最后比较 `sum == x`。 - **主函数**： - 输入 `n`。 - 遍历 `2` 到 `n`，对每个数调用 `isPerfect` 判断，若为完全数则输出。 --- ## 📊 测试样例 输入： ``` 100 ``` 输出： ``` 6 28 ``` 输入： ``` 10000 ``` 输出： ``` 6 28 496 8128 ``` --- ## ⚠️ 注意事项与优化建议 1. **n 很大时（如 ≥ 10^7）**，此算法可能较慢。此时建议使用数学性质：目前已知的完全数都是偶完全数，公式为 `2^(p-1) * (2^p - 1)`，其中 `2^p - 1` 是梅森素数。可以先枚举小的梅森素数来快速生成完全数。 2. **1的处理**：题目要求2到n，所以从2开始即可，不需要特判1。 3. **因子求和边界**：使用 `sqrt` 时必须注意整数转换和避免重复加平方根。 4. **输入范围**：根据题目要求，n为正整数，但若n<6则无输出，也属正常。 --- ## 📚 相关扩展学习 - 梅森素数与完全数的关系：<https://zh.wikipedia.org/wiki/梅森素数> - C++ 性能优化基础：<https://cplusplus.com/doc/tutorial/> - 欧几里得-欧拉定理：所有偶完全数都可由梅森素数生成 --- 希望这份解析对你有帮助！如果还有关于此题的疑问，欢迎继续提问。😊 ######[AI写代码神器 | 992点数解答 | 2026-08-16 17:48:17]