旅游了2天，回来顺便把这道题AC了。
题目中告诉了一个区间：这个区间极值分别为-1e9和1e9（这个是测试数据逗你玩的，实际题目不可能有负数的），区间两端距离最大为1e6。
题目中说了l或r∉[1,m]输出 Crossing the line，那么题目转化为求l~r之间的素数个数，l最小为1，r最大为1e6。
可以考虑开个1e6的数组存下0~1e6之间所有的素数，用埃式筛法过筛，sum累加一下即可。sum[r]-sum[l]就是答案。
有一个要点——注意区间开闭：一个区间比如[2,9]，单纯sum[r]-sum[l]得到答案3，其实2也是素数，不过被减去了，就要特判左端区间是否为素数，是则答案+1。不这样的话只能拿36分。
#include<bits/stdc++.h> using namespace std; int n,m,l,r,sum[1000005],t; bool a[1000005]= {1,1}; int main() { scanf("%d%d",&n,&m); for(int i=2; i<=m; i++) for(int j=i; j<=m; j=j+i) if(i%j!=0)a[j]=1; for(int i=1; i<=m; i++) if(!a[i])sum[i]++; for(int i=1; i<=m; i++) sum[i]+=sum[i-1]; for(int i=1; i<=n; i++) { scanf("%d%d",&l,&r); if(l>m||l<1||r>m||r<1) { cout<<"Crossing the line"<<endl; continue; } if(r==1) { cout<<0<<endl; continue; } t=sum[r]-sum[l]; if(!a[l])t++; printf("%d\n",t); } return 0; }
原文：https://www.cnblogs.com/yige2019/p/11291485.html
