题解 | 质数统计

本题查询次数多范围也比较大，如果一个一个找会超时的，所以我们考虑用素数筛预处理出查询范围内所有的素数，然后运用前缀和加速查询速度。

#include <bits/stdc++.h>
using namespace std;

const int N = 1000006;
int b[N] , j , s[N];                //b是素数数组，j是素数个数，s是前缀和数组
bool a[N];                          //标记合数数组

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0) , cout.tie(0);
    //欧拉筛
    for(int i = 2 ; i < N ; i ++){
        if(!a[i]){
            b[++ j] = i;
            s[i] ++;                //在筛出一个素数时进行前缀和标记
        }
        for(int q = 1 ; q <= j && i * b[q] < N ; q ++){
            a[i * b[q]] = 1;
            if(!(i % b[q]))
                break;
        }
    }
    a[1] = 1;
    for(int i = 1 ; i < N ; i ++)
        s[i] += s[i - 1];
    int n;
    cin >> n;
    while(n --){
        int l , r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << '\n';
    }
    return 0;
}