P1865 A % B Problem

容易超时，需要预处理素数表

#include <bits/stdc++.h>
using namespace std;
bool isp[1000005]={true,true};
int n,m,l,r,sum[1000005];
void init(){
    for(int i=2;i<=1000;i++){
        if(!isp[i]){
            for(int j=i*i;j<=1000000;j+=i){
                if(!isp[j]) isp[j]=true;
            }
        }
    }
    for(int i=2;i<=1000000;i++){
        if(!isp[i]) sum[i]=sum[i-1]+1;
        else sum[i]=sum[i-1];
    }
}
int main(){
    init();
    cin>>n>>m;
    while(n--){
        cin>>l>>r;
        if(l>=1&&l<=m&&r>=1&&r<=m) cout<<sum[r]-sum[l]+!isp[l]<<endl;
        else cout<<"Crossing the line\n";
    }
    return 0;
}