C++计算区间内整数因数之和的完整实现与优化策略

## 📝 问题解析 这个题目要求计算从 **m** 到 **n** 每个整数的**所有因数之和**，并按要求输出结果。下面我会给出 **C++ 实现方案**，并解释关键点。 --- ### 🔧 方案一：基础做法（逐个计算因数） 这是最直观的方法：对每个数 `i`，遍历从 `1` 到 `i`，检查是否能整除。 ```cpp #include <iostream> using namespace std; // 计算单个数的因数之和（基础版） int sumOfDivisors(int x) { int sum = 0; for (int i = 1; i <= x; ++i) { if (x % i == 0) { sum += i; } } return sum; } int main() { int m, n; cin >> m >> n; for (int i = m; i <= n; ++i) { cout << "因数之和(" << i << ") = " << sumOfDivisors(i) << endl; } return 0; } ``` --- ### ⚡ 方案二：优化版（只需遍历到 sqrt(x)） 因数成对出现，所以只需检查到 `sqrt(x)`，性能大幅提升。 ```cpp #include <iostream> #include <cmath> using namespace std; // 优化版：利用对称性，只需遍历到 sqrt(x) int sumOfDivisorsOptimized(int x) { int sum = 0; int limit = (int)sqrt(x); for (int i = 1; i <= limit; ++i) { if (x % i == 0) { sum += i; if (i != x / i) { // 避免重复添加平方数因子（如 4 的因子 2） sum += x / i; } } } return sum; } int main() { int m, n; cout << "请输入 m 和 n（m ≤ n）："; cin >> m >> n; for (int i = m; i <= n; ++i) { cout << i << " 的因数之和 = " << sumOfDivisorsOptimized(i) << endl; } return 0; } ``` --- ### 📊 算法复杂度对比 | 方案 | 时间复杂度 | 适用场景 | |------|------------|----------| | 基础版 | O(n × x) | 数值小，简单易懂 | | 优化版 | O(n × √x) | 通用，推荐使用 | --- ### 🚨 注意事项与边界处理 1. **输入验证**：确保 `m ≤ n`，否则输出错误提示。 2. **耗时优化**：如果 `n - m` 很大（如百万级），可以考虑使用 **前缀和** 或 **筛法**，但一般情况下 √n 优化已足够。 3. **整数溢出**：若数字较大（如 10^9），因数之和可能超出 `int` 范围，建议改用 `long long`。 4. **平方数特殊情况**：因子 `sqrt(x)` 只能加一次，必须判断是否相等。 --- ### 💡 进阶建议 如果需要进一步优化，可以**预处理素数表**，快速分解质因数，然后用公式计算因数之和： > 若 `x = p1^a1 * p2^a2 * ... * pk^ak`，则因数之和 = `(p1^(a1+1)-1)/(p1-1) * ...` 这样复杂度可降至 **O(log x)**，适合大规模计算。 --- ### 📚 测试样例 **输入**：`m = 1, n = 10` **输出示例**： ``` 1 的因数之和 = 1 2 的因数之和 = 3 3 的因数之和 = 4 4 的因数之和 = 7 5 的因数之和 = 6 6 的因数之和 = 12 7 的因数之和 = 8 8 的因数之和 = 15 9 的因数之和 = 13 10 的因数之和 = 18 ``` --- ### ✅ - **首选优化版**，代码清晰且高效。 - 注意使用 `long long` 防止溢出。 - 如果需在竞赛中使用，推荐结合素数筛 + 公式法。 ######[AI写代码神器 | 967点数解答 | 2026-08-23 17:41:31]