C++ 实现区间整数因数之和计算及代码优化

好的，我们来分析并解决这个问题。 ### 问题分析 1. **理解“因数之和”**：对于一个整数 `k`，它的因数（也叫约数）是指能整除 `k` 的所有正整数。例如，`4` 的因数有 `1, 2, 4`，它们的和是 `1 + 2 + 4 = 7`。 2. **理解题目要求**：题目要求计算从 `m` 到 `n`（包含 `m` 和 `n`）每个数的因数之和，然后再把这些和加起来。 * 对于样例 `m=2, n=4`： * 2 的因数：1, 2 → 和为 3 * 3 的因数：1, 3 → 和为 4 * 4 的因数：1, 2, 4 → 和为 7 * 总因数之和：3 + 4 + 7 = 14。这与输出样例一致。 ### 解决方案 为了高效且清晰地解决这个问题，我们可以分两步走： 1. **计算单个数的因数之和**：创建一个函数，遍历从 1 到该数的所有整数，判断是否能整除，并累加。 2. **累加范围总和**：在主函数中，遍历从 `m` 到 `n` 的所有整数，调用第一步的函数，将结果累加。 ### 🔨 代码实现 ```cpp #include <iostream> using namespace std; // 函数：计算一个整数 n 的因数之和 int sumOfDivisors(int num) { int sum = 0; // 从 1 遍历到 num，判断是否能整除 for (int i = 1; i <= num; ++i) { if (num % i == 0) { sum += i; } } return sum; } int main() { int m, n; // 读取输入 cin >> m >> n; int totalSum = 0; // 遍历从 m 到 n 的所有整数 for (int i = m; i <= n; ++i) { totalSum += sumOfDivisors(i); } // 输出结果 cout << totalSum << endl; return 0; } ``` ### 🔍 关键步骤解释 1. **`int sumOfDivisors(int num)` 函数**： * `int sum = 0;`：初始化因数之和为 0。 * `for (int i = 1; i <= num; ++i)`：从 1 开始循环到 `num` 本身，检查每一个数是否是因数。 * `if (num % i == 0)`：`%` 是 C++ 的取模运算符，如果 `num % i` 结果为 0，说明 `i` 能整除 `num`，即 `i` 是 `num` 的因数。 * `sum += i;`：将找到的因数累加到 `sum` 中。 2. **主函数 `main()`**： * `cin >> m >> n;`：从标准输入读取两个整数。 * `int totalSum = 0;`：初始化最终结果为 0。 * `for (int i = m; i <= n; ++i)`：循环遍历 `m` 到 `n` 的每个整数。 * `totalSum += sumOfDivisors(i);`：调用函数计算当前整数 `i` 的因数之和，并加到总数上。 * `cout << totalSum << endl;`：输出最终计算的总和。 ### 🚀 性能优化建议 对于题目的数据范围（`m, n ≤ 1000`），上述 `O(n * sqrt(n))`? 不，是 `O(n²)`? 更准确地说，对于每个数都检查到其自身，时间复杂度是 `O(n*m)`，对于最大 `1000` 完全没有问题。 **但如果要提升，可以这样做**： * **优化因数计算**：计算一个数 `num` 的因数时，不需要循环到 `num`，只需要循环到 `sqrt(num)`。 * 如果 `i` 是 `num` 的因数，那么 `num / i` 也是 `num` 的因数（除非 `i == num / i`）。 * 这样可以大幅提升大数时的性能。 * **示例优化版**： ```cpp int sumOfDivisorsOptimized(int num) { int sum = 0; int sqrtNum = (int) sqrt(num); for (int i = 1; i <= sqrtNum; ++i) { if (num % i == 0) { sum += i; // 加上小因数 if (i != num / i) { sum += num / i; // 加上匹配的大因数 } } } return sum; } ``` 对于当前 `≤1000` 的数据范围，基础版本已经足够快且更容易理解。 ### 👨‍💻 开发建议 1. **代码风格**：保持代码结构清晰，将功能模块化（如将因数求和写成函数），便于测试和维护。 2. **数据类型**：由于 `m, n ≤ 1000`，每个数的因数之和最大可能是 `1000` 本身，总和最大可能接近 `1000 * 1000 = 1,000,000`，在 `int` 范围内，所以使用 `int` 是安全的。 3. **边界检查**：虽然题目保证 `m ≤ n`，但在实际开发中，最好增加一些输入校验，例如检查 `m` 是否小于等于 `n`。 4. **头文件**：**<iostream>** 是 C++ 标准输入输出流，**<cmath>** 在优化版本中用于 `sqrt` 函数。 ### 📚 学习资源 * **C++ 基础**：菜鸟教程 C++ 教程 (C++ 基础语法) * **算法优化**：LeetCode 或 HackerRank 上的入门数学/数论题。 ######[AI写代码神器 | 1370点数解答 | 2026-06-20 19:16:48]