C++高效计算区间因数之和：筛法实现与数论优化指南

## 🛡️ 问题分析 您需要计算从 **m 到 n**（含两端）所有数字的**因数之和**。这里“因数之和”指**真因数之和**（排除数字本身）还是**包含自身**的因数之和？常见算法题通常指**真因数之和**（如欧拉函数变体），但为明确性，我先实现两种版本，并说明区别。 **⚠️ 关键定义** - **包含自身**：如 6 的因数之和 = 1+2+3+6 = 12 - **真因数**（排除自身）：如 6 的真因数之和 = 1+2+3 = 6（若为完美数，则等于自身） --- ## ⚙️ 核心算法思路 ### 📌 朴素方法（适合小范围） 对每个数 i 从 1 到 √i 遍历，找到成对因数并累加。时间复杂度 **O((n-m)√n)**，若 m、n 很大（如百万级）会较慢。 ### 📌 高效筛法（推荐） 利用**倍数累加**思想，一次性计算区间内所有数的因数之和，时间复杂度 **O(n log n)**，适合 n 达 10^7 量级。 --- ## 💻 C++ 实现（高效筛法） ```cpp #include <iostream> #include <vector> #include <numeric> // 用于accumulate（可选） /** * 计算 [1, n] 所有数包含自身的因数之和 */ std::vector<long long> computeDivisorSumIncludingSelf(int n) { std::vector<long long> sum(n + 1, 0); for (int i = 1; i <= n; ++i) { for (int j = i; j <= n; j += i) { sum[j] += i; // i 是 j 的一个因数 } } return sum; } /** * 计算 [1, n] 所有数的真因数之和（排除自身） */ std::vector<long long> computeProperDivisorSum(int n) { std::vector<long long> sum(n + 1, 0); for (int i = 1; i <= n; ++i) { for (int j = i * 2; j <= n; j += i) { sum[j] += i; // 从 2*i 开始，避免累加自身 } } return sum; } int main() { int m = 1, n = 100; bool includeSelf = false; // 改为 true 则包含自身 // 根据需要选择函数 auto sumVec = includeSelf ? computeDivisorSumIncludingSelf(n) : computeProperDivisorSum(n); long long total = 0; for (int i = m; i <= n; ++i) { total += sumVec[i]; } std::cout << "从 " << m << " 到 " << n << " 的因数之和（" << (includeSelf ? "包含自身" : "真因数") << "）为: " << total << std::endl; return 0; } ``` --- ## 🧮 复杂度与优化 | 方法 | 时间复杂度 | 空间复杂度 | 适用规模 | |------|------------|------------|----------| | 朴素遍历 | O((n-m)√n) | O(1) | n ≤ 10^5 | | 筛法 | O(n log n) | O(n) | n ≤ 10^7 | **💡 优化建议**： - 若只查询单次区间，且 n 较大，**直接筛法**更优。 - 若多次查询不同区间，可**预处理前缀和**，将总查询降为 O(1)： ```cpp std::vector<long long> prefix(n + 1, 0); for (int i = 1; i <= n; ++i) prefix[i] = prefix[i-1] + sumVec[i]; // 区间 [m,n] 结果为 prefix[n] - prefix[m-1] ``` --- ## 🧪 测试示例 运行上述代码（`includeSelf = false`）： - 输入 m=1, n=10 → 真因数之和 = 0+1+1+3+1+6+1+7+4+8 = **32** - 输入 m=1, n=6 → 真因数之和 = 0+1+1+3+1+6 = **12** --- ## ⚠️ 常见陷阱与注意事项 - **数据类型**：因数之和可能较大，使用 `long long` 避免溢出。 - **边界值**：m 必须 ≥ 1，若 m=0 需特殊处理（0 的因数未定义）。 - **内存优化**：若 n 超 10^8，则无法用 vector，需改用分段筛选或数学公式（如质因数分解后计算）。 --- ## 📚 进阶扩展 ### 🔢 基于质因数分解的公式 若需单个数的高效因数之和，可先分解质因数： - 若 n = p₁^a₁ * p₂^a₂ * ... - **包含自身**的因数之和 = ∏ (pᵢ^(aᵢ+1) - 1) / (pᵢ - 1) - **真因数之和** = 上式 - n ### 🧠 其他应用场景 - 判断**完美数**（真因数之和 == 自身） - **亲和数** 配对检测 - 数论问题如「过剩数」「亏数」统计 --- ## 📖 学习资源推荐 - **C++ 参考**：[cppreference.com](https://en.cppreference.com)（vector、循环优化） - **数论基础**：欧拉筛、约数个数定理 - **练习平台**：LeetCode（如 [#2114. Maximum Number of Words Found in Sentences] 无关，但可搜 divisor sum），或 Project Euler 第 21 题（亲和数） --- ## 🛠 开发建议 1. **性能测试**：用 `std::chrono` 测量大 n 的性能，选择性优化内层循环（如使用步长 i）。 2. **模块化**：将筛选函数独立成工具类，便于复用和单元测试。 3. **并行化**：若 n 极大，可考虑 OpenMP 并行化外层循环（注意数据竞争需原子操作）。 若您需要更具体的场景（如 n 达 10^8），请告知，我可提供**分段筛法**或**数学公式法**的完整实现。 --- ######[AI写代码神器 | 1495点数解答 | 2026-08-23 18:24:42]