题解 | 质数统计

#include <iostream>
using namespace std;
const int N=1e6;
bool st [N];
int primes[N];
int count[N];
void solve ( ){
    int ans=0;
    for(int i=2;i<=N;i++){
          if(!st[i])   primes[ans++]=i;     
            for(int j=0;primes[j]<=N/i;j++){
                st[primes[j]*i]=true;
                if(i%primes[j]==0) break;
            }
     count[i]=ans;
    // cout<<i<<" "<<ans<<endl;
    }
    
}




int main() {
   
int n;
cin>>n;
solve();
while(n--){
    int l,r;
    cin>>l>>r;
    cout<<count[r]-count[l-1]<<endl;
}

}