题解 | 质数统计

#include <iostream>
using namespace std;

long long re(int a){

    if(a==1){
        return 0;
    }
    if(a==2){
        return 1;
    }
    if(a%2==0){
        return 0;
    }
    for(int i=2;i*i<=a;i++){

        if(a%i==0){
            return 0;
        }
    }
    return 1;
}
int b[1000008];

int main(){

int n;
cin>>n;
for(int i=1;i<=1000000;i++){
b[i]=b[i-1]+re(i);
}
while(n--){
int l,r;
cin>>l>>r;

cout<<b[r]-b[l-1]<<endl;








}

    return 0;
}