C++求1到n每个数的因数个数：筛法实现与线性筛优化

## 🔢 问题理解 您提到的“P3772因数个数”可能指洛谷（Luogu）上的题目 P3772（“因数个数”），该题要求计算给定区间内每个数的因数个数。由于题目描述未完整给出，以下基于常见解法提供 C++ 实现。 ## 💻 C++ 解法示例 若题目要求计算 1 到 n 中每个数的因数个数，常见做法是使用**筛法**（类似埃氏筛）预处理。 ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<int> divCnt(n + 1, 0); // 枚举 i 作为因数，累加到每个倍数 for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j += i) { divCnt[j]++; } } // 输出每个数的因数个数 for (int i = 1; i <= n; i++) { cout << "数 " << i << " 的因数个数: " << divCnt[i] << endl; } return 0; } ``` ## 🧠 算法说明 - 外层循环 `i` 从 1 到 n，内层循环枚举 `i` 的所有倍数。 - 每个数 `j` 会被其所有因数 `i` 更新一次，因此 `divCnt[j]` 最终等于 `j` 的因数总个数。 - 时间复杂度 O(n log n)，空间复杂度 O(n)。 ## ⏱️ 优化变体（若需处理大范围） 若 n 很大（如 10^7），可用线性筛法求每个数的最小质因数，再结合质因数分解计算因数个数。 ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<int> spf(n + 1, 0); // 最小质因子 vector<int> primes; // 线性筛构建最小质因子 for (int i = 2; i <= n; i++) { if (spf[i] == 0) { spf[i] = i; primes.push_back(i); } for (int p : primes) { if (p > spf[i] || i * p > n) break; spf[i * p] = p; } } vector<int> divCnt(n + 1, 1); for (int i = 2; i <= n; i++) { int x = i; int cnt = 1; // 分解质因数并计算因数个数 while (x > 1) { int p = spf[x]; int exp = 0; while (x % p == 0) { x /= p; exp++; } cnt *= (exp + 1); } divCnt[i] = cnt; } for (int i = 1; i <= n; i++) { cout << i << ": " << divCnt[i] << endl; } return 0; } ``` ## 📌 注意事项 - 若题目要求区间查询（如 [L, R]），可以先预处理前缀和或直接查询时计算。 - 注意数据范围，避免使用递归或过深循环导致超时。 - 如果 P3772 具体描述不同（如询问单个数的因数个数），请提供完整题目内容以便调整代码。 ######[AI问答 | 800点数解答 | 2026-08-23 18:54:22]