不用前缀和

#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
int n,m;
const int N=1e6+6;
bool isprime[N+1];
void sieve(){
    fill(isprime,isprime+N+1,true);
    isprime[0]=isprime[1]=false;
	for(int i=2;i<=N;i++){
		if(isprime[i]){
			for(ll j=(ll)i*i;j<=N;j+=i){
				isprime[j]=false;
			}
		}
	}
}
int main(){
    sieve();
    cin>>n>>m;
    while(n--){
        int l,r;
        cin>>l>>r;
        int cnt=0;
        for(int i=l;i<=r;i++){
            if(isprime[i]==true) cnt++;
        }
        cout<<cnt<<endl;
    }
}