题解 | 质数统计

#include <bits/stdc++.h>
using namespace std;
int main() {
    const int maxn = 1000005;
    bool prime[maxn];
    int pre[maxn];
    int n;
    cin >> n;
    //先将所有定义为质数
    for(int i = 0;i < maxn;i++){
        prime[i] = true;
    }
    //数组第一位和数字1去掉
    prime[0] = prime[1] = false;
    //将质数的倍数去掉，从2开始
    for(int i = 2;i < maxn;i++){
        if(prime[i]){
            for(int j = i+i;j < maxn;j += i){
                prime[j] = false;
            }
        }
    }
    //前缀和
    pre[0] = 0;
    for(int i = 1;i < maxn;i++){
        pre[i]=pre[i-1]+(prime[i]?1:0);
    }
    //区间查询
    int ans = 0;
    for(int i = 1;i <= n;i++){
        int l,r;
        cin >> l>> r;
        ans = pre[r] - pre[l-1];
        cout<<ans<<endl;
    }

}