题解 | 质数统计

一开始想用线段树来做的，但是发现是杀鸡用牛刀了，用前缀和就可以轻松ac

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
using i128 = __int128;
const int MOD = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 10;

void solve()
{
    vector<bool> isprime(1000007);
    isprime[1]=isprime[0]=true;
    vector<int> prime(1000003);
    int cnt = 1;
    for (int i=2;i<1000003;i++) 
    {
        if (!isprime[i]) prime[cnt++]=i;
        for (int j=1;j<=cnt;j++)
        {
            if (i*prime[j]>1000003) break;
            isprime[i*prime[j]]=true;
            if (i%prime[j] == 0) break;
        }
    }
    vector<int> pre(1000004);
    for (int i = 0 ; i < 1000003 ; i++)
    {
        if (!isprime[i])
        {
            pre[i + 1] = pre[i] + 1;
        }
        else pre[i + 1] = pre[i];
    }
    int n;
    cin>>n;
    while (n--)
    {
        int l,r;
        cin>>l>>r;
        cout<<pre[r + 1] - pre[l]<<'\n';
    }
    return;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int _ = 1;
    //std::cin>>_;
    while (_--)
    {
        solve();
    }
    return 0;
}