题目描述
区间质数个数
输入输出格式
输入格式：
一行两个整数 询问次数n，范围m
接下来n行，每行两个整数 l,r 表示区间
输出格式：
对于每次询问输出个数 t，如l或r∉[1,m]输出 Crossing the line
输入输出样例
输入样例#1：
2 51 32 6
输出样例#1：
2Crossing the line
说明
【数据范围和约定】
对于20%的数据 1<=n<=10 1<=m<=10
对于100%的数据 1<=n<=1000 1<=m<=1000000 -10^9<=l<=r<=10^9 1<=t<=1000000
#includeusing namespace std;//input by bxd#define rep(i,a,b) for(int i=(a);i<=(b);i++)#define repp(i,a,b) for(int i=(a);i>=(b);i--)#define RI(n) scanf("%d",&(n))#define RII(n,m) scanf("%d%d",&n,&m)#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)#define RS(s) scanf("%s",s);#define LL long long#define pb push_back#define fi first#define REP(i,N) for(int i=0;i<(N);i++)#define CLR(A,v) memset(A,v,sizeof A)///#define inf 0x3f3f3f3f#define N 100000000+5int s,e;int f[N];int a[N];void prime(){ //0代表是素数 1代表不是素数 最好这样反过来 节省初始化为1的时间 a[1]=1; for(int i=2;i*i<=e;i++) { if(a[i]==0) for(int j=i*i;j<=e;j+=i) a[j]=1; } rep(i,2,e) { f[i]=f[i-1]; if(a[i]==0)f[i]++; }}int main(){ int n; RII(n,e); prime(); rep(i,1,n) { int a,b; RII(a,b); if(a<1||b>e)printf("Crossing the line\n"); else printf("%d\n",f[b]-f[a-1]); } return 0;}
