C++ 求正整数所有因数和：两种高效实现方法详解

好的，这是一个非常经典的算法题。我将从 **问题分析**、**基础实现**、**优化方案** 以及 **C++ 代码示例** 几个方面为你详细解答。 ## 💡 问题分析 题目要求：给定一个正整数 `n`，求出它所有因数（包括 1 和自身）的和。 **关键概念：** - **因数（约数）**：如果整数 `a` 能被整数 `b` 整除（`a % b == 0`），则 `b` 是 `a` 的因数。 - **数学规律**：因数通常成对出现。例如，`n = 12` 的因数有 `(1, 12)`, `(2, 6)`, `(3, 4)`。 - **平方数处理**：如果 `n` 是完全平方数，例如 `n = 16`，因数 `4` 会出现两次，但只能计算一次。 ## 🚀 解法一：暴力枚举（最直接） 最直观的方法是遍历 `1` 到 `n`，判断每个数是否能整除 `n`。 **复杂度分析：** - 时间复杂度：`O(n)` - 空间复杂度：`O(1)` **优点：** 实现简单，无需额外思考。 **缺点：** 当 `n` 很大时（如 `10^12`）会超时。 ### 📝 C++ 代码示例（暴力法） ```cpp #include <iostream> using namespace std; int main() { long long n; cin >> n; long long sum = 0; for (long long i = 1; i <= n; ++i) { if (n % i == 0) { sum += i; } } cout << sum << endl; return 0; } ``` ## ⚡ 解法二：优化枚举（推荐） 利用因数的成对性质，我们只需遍历 `1` 到 `√n`。 **核心思想：** - 如果 `i` 是 `n` 的因数（`n % i == 0`），那么 `n / i` 也是 `n` 的因数。 - 当 `i` 和 `n / i` 相等时（即 `i * i == n`，完全平方数），只加一次。 **复杂度分析：** - 时间复杂度：`O(√n)` - 空间复杂度：`O(1)` **优点：** 效率大幅提升，可处理 `10^12` 级别数据。 **缺点：** 需要考虑边界情况（平方数）。 ### 📝 C++ 代码示例（优化枚举） ```cpp #include <iostream> #include <cmath> using namespace std; int main() { long long n; cin >> n; long long sum = 0; long long sqrt_n = sqrt(n); for (long long i = 1; i <= sqrt_n; ++i) { if (n % i == 0) { sum += i; // 加上较小的因数 i if (i != n / i) { // 避免平方数重复 sum += n / i; // 加上对应的较大因数 } } } cout << sum << endl; return 0; } ``` ## 🧪 进阶思考：质因数分解法 对于需要频繁计算因数和或处理超大数（如 `10^18`）的场景，可以使用 **质因数分解** 结合公式： **数学公式：** 如果 `n` 的质因数分解为：`n = p1^a1 * p2^a2 * ... * pk^ak` 则因数和为：`(p1^(a1+1) - 1)/(p1 - 1) * (p2^(a2+1) - 1)/(p2 - 1) * ...` **适用场景：** 需要处理多个不同 `n` 的因数和问题时，可以预计算质数表加速。 ## 📋 测试样例 | 输入 n | 因数 | 因数和 | 说明 | |--------|------|--------|------| | 1 | 1 | 1 | 特殊情况 | | 2 | 1, 2 | 3 | 质数 | | 4 | 1, 2, 4 | 7 | 平方数 | | 6 | 1, 2, 3, 6 | 12 | 完全数 | | 12 | 1,2,3,4,6,12 | 28 | 通用情况 | | 100 | 1,2,4,5,10,20,25,50,100 | 217 | 较大平方数 | ## 💻 开发建议 1. **数据类型选择：** 使用 `long long` 而不是 `int`，因为 `n` 最大可达 `10^12`，因数之和可能超过 `int` 范围。 2. **避免浮点数陷阱：** 使用 `sqrt(n)` 后，建议用 `i * i <= n` 替代循环条件，完全避免浮点误差。 3. **代码健壮性：** 处理 `n = 1` 的边界情况时，优化算法依然正确，因为循环条件 `i <= sqrt(1) = 1` 会执行一次，判断 `1 % 1 == 0` 成立，且 `1 != 1/1` 为假，只加一次。 4. **对于竞赛编程：** 如果时间限制严格（如 1000MS），优化法完全满足需求，暴力法在 `n = 10^12` 时会严重超时。 希望这个解答对你有所帮助！如果你需要调整代码风格、添加注释或进行其他优化，欢迎继续提问。 ######[AI写代码神器 | 1292点数解答 | 2026-06-07 14:11:51]