C++正整数因数求和算法详解及优化实现

## 🔍 因数求和算法解析 对于正整数 n，因数是能整除 n 的所有正整数。求和即可得出结果。 ### 💡 核心思路 遍历从 1 到 n 的每个整数，检查是否能整除 n。若能整除，则累加到总和。 ### ⚙️ 时间复杂度 朴素遍历 O(n) 在 n 较大时性能不佳。优化方案：遍历到 √n，每次发现因数 i 时同时累加 i 和 n/i。 ### 🧩 C++ 实现（朴素版） ```cpp #include <iostream> using namespace std; int main() { int n; cin >> n; int sum = 0; for (int i = 1; i <= n; ++i) { if (n % i == 0) sum += i; } cout << sum << endl; return 0; } ``` ### 🚀 优化版（√n 遍历） ```cpp #include <iostream> #include <cmath> using namespace std; int main() { int n; cin >> n; int sum = 0; for (int i = 1; i * i <= n; ++i) { if (n % i == 0) { sum += i; if (i != n / i) sum += n / i; } } cout << sum << endl; return 0; } ``` ### 📊 样例验证 输入 4： - 朴素版：i=1,2,4 → 1+2+4=7 - 优化版：i=1 → 累加1和4；i=2 → 累加2（2≠2，不重复加）→ 7 ### 🧮 边界考虑 - n 为 1 时，因数和为 1 - 使用 int 时注意 n 最大为 2^31-1，但因数个数较多时和可能溢出，可改用 long long ### 🎯 复杂度对比 | 版本 | 时间复杂度 | 适用场景 | |------|------------|----------| | 朴素版 | O(n) | n ≤ 10^7 | | 优化版 | O(√n) | n ≤ 10^14 | ######[AI问答 | 516点数解答 | 2026-08-15 23:46:59]