分段筛法：高效计算区间 [L, R] 内素数个数（附代码与思路详解）

```cpp #include <iostream> #include <vector> #include <cmath> using namespace std; int main() { long long L, R; cin >> L >> R; // 处理边界：确保L至少为2 if (L < 2) L = 2; if (R < 2) { cout << 0 << endl; return 0; } // 筛出[2, sqrt(R)]内的素数 int limit = sqrt(R); vector<bool> isPrimeSmall(limit + 1, true); vector<long long> primes; for (int i = 2; i <= limit; ++i) { if (isPrimeSmall[i]) { primes.push_back(i); for (int j = i * i; j <= limit; j += i) { isPrimeSmall[j] = false; } } } // 筛[L, R]区间 vector<bool> isPrimeLarge(R - L + 1, true); for (long long p : primes) { // 找到第一个大于等于L的p的倍数 long long start = max(p * p, (L + p - 1) / p * p); for (long long j = start; j <= R; j += p) { isPrimeLarge[j - L] = false; } } // 统计素数个数 int count = 0; for (long long i = L; i <= R; ++i) { if (isPrimeLarge[i - L]) { count++; } } cout << count << endl; return 0; } ``` 算法思路： 1. 使用埃拉托斯特尼筛法，但直接筛到2^31会超内存。 2. 利用区间长度≤10^6的特点，采用分段筛法： - 先筛出[2, sqrt(R)]内的所有素数 - 用这些素数去标记[L, R]区间内的合数 3. 注意处理L=1的特殊情况，1不是素数 4. 注意long long类型防止溢出 时间复杂度： O((R-L+1)loglogR + √R loglog√R) 空间复杂度： O(√R + (R-L+1)) 关键点： - 筛小素数时从i*i开始标记 - 筛大区间时从max(p*p, ceil(L/p)*p)开始标记 - 使用vector<bool>节省内存 ######[AI问答 | 559点数解答 | 2026-01-18 12:47:23]