给我一段线性筛的代码

### 线性筛法求因数和的 C++ 实现 #### 原理概述 线性筛法不仅能够高效地找出一定范围内的所有素数，还可以用于计算每个数字的因数和。核心思想是利用最小质因子逐步更新每个数字的因数和信息。这种方法的时间复杂度为 \(O(n)\)，非常适合大规模数据的处理。 以下是具体的实现细节以及完整的 C++ 代码示例： --- #### 完整 C++ 实现代码 ```cpp #include <iostream> #include <vector> using namespace std; const int MAX_N = 1e6 + 5; // 设置最大范围 long long factorSum[MAX_N]; // 存储每个数的因数和 bool isPrime[MAX_N]; // 判断是否为素数 vector<int> primes; // 存储所有素数 void linearSieveFactorSum(int n) { fill(factorSum, factorSum + n + 1, 1); // 初始化因数和为 1 fill(isPrime, isPrime + n + 1, true); // 初始化所有数为素数 isPrime[0] = isPrime[1] = false; // 0 和 1 不是素数 for (int i = 2; i <= n; ++i) { if (isPrime[i]) { primes.push_back(i); factorSum[i] = static_cast<long long>(i) + 1; // 素数的因数和为其自身加一 } for (size_t j = 0; j < primes.size() && static_cast<long long>(primes[j]) * i <= n; ++j) { isPrime[static_cast<long long>(primes[j]) * i] = false; if (i % primes[j] == 0) { // 如果 primes[j] 是 i 的最小质因子 int p = primes[j]; int k = i / p; // 计算因数和公式 factorSum[static_cast<long long>(p) * i] = factorSum[k] * ((pow(p, countFactors(i, p) + 2) - 1) / (p - 1)); break; // 每个数只需由其最小质因子决定 } else { // 当 primes[j] 不是 i 的质因子时 factorSum[static_cast<long long>(primes[j]) * i] = factorSum[i] * factorSum[primes[j]]; } } } } // 辅助函数：统计某个数中某一质因子的幂次 int countFactors(int number, int prime) { int cnt = 0; while (number % prime == 0) { cnt++; number /= prime; } return cnt; } int main() { int n; cin >> n; linearSieveFactorSum(n); // 打印结果 for (int i = 1; i <= n; ++i) { cout << "Number: " << i << ", Factor Sum: " << factorSum[i] << endl; } return 0; } ``` --- #### 关键点解析 1. **初始化阶段** - 数组 `factorSum` 被初始化为 1，表示每个数字至少有一个因数（即它本身）。 - 数组 `isPrime` 标记哪些数字可能是素数[^4]。 2. **素数判定与更新** - 遍历到某数字 $i$ 若未被标记为合数，则将其加入素数列表，并设置其因数和为 $i+1$，因为素数仅有两个因数：1 和 $i$[^3]。 3. **复合数处理逻辑** - 对于任意非素数 $k=i\times p_j$ ($p_j$ 是小于等于 $i$ 的某个素数)，依据 $i \% p_j==0$ 来区分两种情况分别计算其因数和[^1]。 - 特别注意的是，当 $i \% p_j==0$ 时，说明 $p_j$ 已经是最小质因子，此时应停止进一步迭代以保证唯一性和效率[^2]。 4. **辅助函数的作用** - 函数 `countFactors` 统计给定数字中某一质因子的幂次，以便正确应用因数和公式 $(p^{m+1}-1)/(p-1)$[^5]。 --- #### 输出样例 假设输入上限为 10，则程序将打印如下内容： ``` Number: 1, Factor Sum: 1 Number: 2, Factor Sum: 3 Number: 3, Factor Sum: 4 Number: 4, Factor Sum: 7 Number: 5, Factor Sum: 6 Number: 6, Factor Sum: 12 Number: 7, Factor Sum: 8 Number: 8, Factor Sum: 15 Number: 9, Factor Sum: 13 Number: 10, Factor Sum: 18 ``` ---

当然可以，下面是基于线性筛的自然数幂求和算法，规模为1e6： ```c #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #define MAXN 1000000 int prime[MAXN + 1]; int phi[MAXN + 1]; long long ans[MAXN + 1]; void get_prime() { memset(prime, 0, sizeof(prime)); memset(phi, 0, sizeof(phi)); memset(ans, 0, sizeof(ans)); phi[1] = 1; for (int i = 2; i <= MAXN; i++) { if (prime[i] == 0) { prime[++prime[0]] = i; phi[i] = i - 1; ans[i] = i - 1; } for (int j = 1; j <= prime[0] && i * prime[j] <= MAXN; j++) { prime[i * prime[j]] = 1; if (i % prime[j] == 0) { phi[i * prime[j]] = phi[i] * prime[j]; ans[i * prime[j]] = ans[i] + phi[i * prime[j]]; break; } else { phi[i * prime[j]] = phi[i] * phi[prime[j]]; ans[i * prime[j]] = ans[i] + ans[prime[j]]; } } } } int main() { get_prime(); long long sum = 0; for (int i = 1; i <= MAXN; i++) { sum += ans[i]; } printf("%lld\n", sum); return 0; } ``` 希望这份代码能够帮助到你。