C++ 统计区间内质因数个数最大值的筛法实现

好的，这个问题是要求统计一个区间内每个数字的**质因数个数**（注意：是质因数，并且是重复计数，比如8=2*2*2，质因数个数为3），然后找出这些个数中的最大值。 下面我为你提供完整的C++解法，包含详细的注释和思路说明。 ## 🧠 问题分析 我们需要计算区间 `[n, m]` 中每个整数 `x` 的质因数总个数（可重复）。 例如： - 4 = 2*2 → 质因数个数 = 2 - 6 = 2*3 → 质因数个数 = 2 - 8 = 2*2*2 → 质因数个数 = 3 - 12 = 2*2*3 → 质因数个数 = 3 然后输出所有这些个数中的最大值。 --- ## 💻 推荐算法：埃氏筛法思想 + DP **核心思路**： 我们可以用类似埃拉托斯特尼筛法的方法，在筛选素数的统计每个数的质因数个数。 **原理**： - 对于每个质数 `p`，它对它的倍数 `i*p` 贡献一个质因数。 - 我们可以用一个数组 `cnt[x]` 来记录 `x` 当前已经累积的质因数个数。 - 遍历 `i` 从 2 到 `m`，如果 `cnt[i] == 0` 说明 `i` 是质数（还未被标记），则从 `j = i` 开始，把 `i` 加到所有倍数 `j` 的计数中，多次加（因为每个倍数都可以被 `i` 整除多次）。 这样一次扫描就可以得到每个数的质因数总个数，时间复杂度为 O(m log log m)，非常高效。 --- ## ✅ 完整 C++ 代码 ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, m; cin >> n >> m; // cnt[i] 表示数字 i 的质因数总个数（可重复计数） vector<int> cnt(m + 1, 0); // 筛法统计质因数个数 for (int i = 2; i <= m; ++i) { if (cnt[i] == 0) { // i 是质数 for (int j = i; j <= m; j += i) { // 计算 j 中能分解出多少个 i int temp = j; while (temp % i == 0) { cnt[j]++; temp /= i; } } } } // 在 [n, m] 区间内找最大值 int maxCount = 0; for (int i = n; i <= m; ++i) { maxCount = max(maxCount, cnt[i]); } cout << maxCount << endl; return 0; } ``` --- ## 🔍 代码解释 1. **输入处理**：读取 `n` 和 `m`。 2. **初始化数组**：`cnt` 大小为 `m+1`，所有元素初始为 0。 3. **筛法核心**： - 当 `cnt[i] == 0` 时，`i` 一定是质数（因为它没有被任何小于它的质数标记过）。 - 对于每个质数 `i`，遍历它的所有倍数 `j`，并不断除以 `i`，直到不能整除，每次除都增加 `cnt[j]`。 4. **结果统计**：遍历 `[n, m]`，取 `cnt` 的最大值。 5. **输出**：打印结果。 --- ## 🧪 示例 输入： ``` 2 10 ``` 计算过程： - 2: 质因数个数 = 1 - 3: 1 - 4: 2 (2*2) - 5: 1 - 6: 2 (2*3) - 7: 1 - 8: 3 (2*2*2) - 9: 2 (3*3) - 10: 2 (2*5) 输出： ``` 3 ``` --- ## ⚙️ 复杂度分析 - **时间复杂度**：O(m log log m)，因为每个质数 `p` 的倍数处理需要 O(m/p) 操作，但是这里还进行了 while 循环，实际接近 O(m log log m)。 - **空间复杂度**：O(m)，用于存储 `cnt` 数组。 --- ## 🧩 进阶与注意事项 - **如果 m 很大**（如 10^7 以上），需要注意 `vector<int>` 的内存开销，可以考虑用 `short` 或 `unsigned char` 来节省空间（因为质因数个数不会太大）。 - **如果不允许重复计数**（即只统计不同质因数个数），只需要将内部 while 循环改为 `if` 加一次计数即可。 - **边界处理**：如果 n = 1，那么 1 的质因数个数为 0，程序不需要特殊处理（因为默认 cnt[1]=0）。 - **优化建议**：可以直接用筛法先得到每个数的最小质因数（spf），然后通过 dp 递推计算质因数个数： - `cnt[i] = cnt[i / spf[i]] + 1` --- ## 📚 学习资源推荐 - [C++ 官方文档 - vector](https://en.cppreference.com/w/cpp/container/vector) - 算法书籍：《算法竞赛入门经典》（刘汝佳）、《挑战程序设计竞赛》 - 在线练习平台：LeetCode、洛谷、Codeforces --- ######[AI写代码神器 | 1257点数解答 | 2026-05-03 08:55:35]