#include<cstdio>
#include<cstring>
using namespace std;
int f[1000005];
bool p[1000005];
void GetPrime(int n){
	memset(p,1,sizeof(p));
	p[1]=0;
	for(int i=2;i<=n;++i){
		if(p[i]){
			f[i]=f[i-1]+1;
			for(int j=i+i;j<=n;j+=i)
				p[j]=0;
		}
		else
			f[i]=f[i-1];
	}
}
int main(){
	int n,m,l,r;
	scanf("%d%d",&n,&m);
	GetPrime(m);
	for(int i=1;i<=n;++i){
		scanf("%d%d",&l,&r);
		if(l<1||r>m){
			printf("Crossing the line\n");
			continue;
		}
		printf("%d",f[r]-f[l]);
	}
	return 0;
}

然后

自己看吧【哭