P2240寻找完全数C++实现及优化详解

好的，这道题是经典的 **“找完全数”** 问题。下面为你提供详细的解题思路、C++ 代码实现以及一些开发上的建议。 ## 🧠 解题思路 题目要求找出 **2 到 n 之间** 的所有完全数，其中完全数的定义是： > 除了自身以外的所有因子之和等于该数本身。 例如： - 6 的因子（除自身外）：1, 2, 3 → 1 + 2 + 3 = 6 ✅ - 28 的因子（除自身外）：1, 2, 4, 7, 14 → 1+2+4+7+14 = 28 ✅ ### 💡 核心计算方法 对于每个数 `i`，我们需要： 1. 找出它所有 **小于 i** 的因子。 2. 将这些因子累加。 3. 判断累加和是否等于 `i`。 **优化小技巧**： - 只需遍历到 `sqrt(i)` 即可找到所有因子（成对出现）。 - 因子 `j` 如果满足 `i % j == 0`，则 `j` 和 `i / j` 都是因子（注意避免重复加 `i` 本身）。 ### 🧪 复杂度分析 - 对于每个数 `i`，检查因子需要 O(√i) 时间。 - 总时间复杂度 O(n√n)，n ≤ 10000 时完全可接受。 --- ## 💻 C++ 代码实现 ```cpp #include <iostream> #include <cmath> using namespace std; int main() { int n; cin >> n; for (int i = 2; i <= n; i++) { int sum = 1; // 1 总是因子 // 从 2 到 sqrt(i) 找因子 for (int j = 2; j * j <= i; j++) { if (i % j == 0) { sum += j; if (j != i / j) { sum += i / j; // 避免重复加平方根 } } } // 注意：完全数不包括 1 本身，所以 sum 初始为 1 是合理的 if (sum == i) { cout << i << endl; } } return 0; } ``` --- ## 📘 代码解释 - **`sum = 1`**：因为 1 是除了自身外每个数都有的因子，我们可以直接从 1 开始累加。 - **循环 `j` 从 2 到 `sqrt(i)`**： - 如果 `i % j == 0`，则 `j` 是因子。 - 对应的 `i/j` 也是因子（除非 `j == i/j`，即 i 是完全平方数时，只加一次）。 - **判断 `sum == i`**：如果累加和等于自身，则输出该数。 --- ## ⚠️ 开发建议与常见陷阱 1. **因子重复问题**：当 `i` 是完全平方数时（如 16），要避免重复加 `4`。代码中通过 `if (j != i/j)` 来避免。 2. **边界条件**：题目要求从 2 开始，所以 `1` 不作为候选数。 3. **性能优化**：如果 n 很大（此题 n ≤ 10000 不用太担心），可以提前用筛法或数学性质减少判断次数。但此题 O(n√n) 足够。 4. **格式化输出**：每行一个数，结尾不要有多余空格。 --- ## 📚 知识拓展 完全数有一些有趣的性质： - 目前已知的完全数都是偶数，且都能表示为 `2^(p-1) * (2^p - 1)` 的形式（其中 `2^p - 1` 是梅森素数）。 - 前几个完全数是：6, 28, 496, 8128, ... 如果你对更高效的算法感兴趣，可以了解 **梅森素数** 的判定方法。 --- 希望这个解答对你有帮助！如果还有其他问题，欢迎随时提问。 ######[AI写代码神器 | 931点数解答 | 2026-08-29 20:10:28]