题目背景

#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>using namespace std;const int N=1000010;int answer[N],pos[N],become_answer;bool vis[N];int block,js,n,m; struct node{	int l,r,num;}E[N];inline int read(){	int x=0;int f=1;char c=getchar();	while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}	while(c>=‘0‘&&c<=‘9‘)x=x*10+c-‘0‘,c=getchar();	return x*f;}inline void important(){	for(int i=2;i<=sqrt(N+1);i++)		if(!vis[i])			for(int j=i*2;j<=N;j+=i)				vis[j]=1;	vis[0]=vis[1]=1;}inline bool cmp(node a,node b){	if(pos[a.l]==pos[b.l])		return a.r<b.r;	else		return a.l<b.l;} inline void add(int x){	if(!vis[x])		become_answer++;}inline void dale(int x){	if(!vis[x])		become_answer--;}inline void MD(){	int l=1,r=1;	for(int i=1;i<=js;i++)	{   int ll=E[i].l,rr=E[i].r;		for(;l<E[i].l;l++)dale(l);		for(;l>E[i].l;l--)add(l-1);		for(;r>E[i].r;r--)dale(r);		for(;r<E[i].r;r++)add(r+1);		answer[E[i].num]=become_answer;	}}int main(){	important();	n=read(),m=read();	for(int i=1;i<=n;i++)	{		int l=read(),r=read();		if(l<1||r<1||l>m||r>m)			answer[i]=-1;		else		{			E[++js].l=l;			E[js].r=r;			E[js].num=i;		}	}	block=sqrt(m);	for(int i=1;i<=m;i++)		pos[i]=(i-1)/block+1;	sort(E+1,E+js+1,cmp);	MD();	for(int i=1;i<=n;i++)		if(answer[i]==-1)			printf("Crossing the line\n");		else			printf("%d\n",answer[i]);				return 0;}

#include <cstdio>#include<iostream>#include<algorithm>const int N=1000005;using namespace std;int n,m,l,r,s[N];int main(){    scanf("%d%d",&n,&m);    for(int i=2;i<=m;i++)s[i]=1;    for(int i=2;i*i<=m;i++)        for(int j=i+i;j<=m;j+=i)            s[j]=0;	for(int i=1;i<=m;i++)     　　　　s[i]+=s[i-1];    while(scanf("%d%d",&l,&r)==2)        (l<1||r>m)?printf("Crossing the line\n"):printf("%d\n",s[r]-s[l-1]);}