题目描述
区间质数个数
输入输出格式
输入格式：
一行两个整数 询问次数n，范围m
接下来n行，每行两个整数 l,r 表示区间
输出格式：
对于每次询问输出个数 t，如l或r∉[1,m]输出 Crossing 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
#include<bits/stdc++.h>
using 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+5
int s,e;
int f[N];
int a[N]; void prime()
{
//0代表是素数 1代表不是素数 最好这样反过来 节省初始化为1的时间
a[]=;
for(int i=;i*i<=e;i++)
{
if(a[i]==)
for(int j=i*i;j<=e;j+=i)
a[j]=;
}
rep(i,,e)
{
f[i]=f[i-];
if(a[i]==)f[i]++;
}
}
int main()
{
int n;
RII(n,e);
prime();
rep(i,,n)
{
int a,b;
RII(a,b);
if(a<||b>e)printf("Crossing the line\n");
else printf("%d\n",f[b]-f[a-]);
}
return ;
}