题目描述
给定 l,r，求区间 [l,r] 内质数的个数。
输入格式
第一行有两个整数，分别代表询问次数 n 和 给定区间的右端点最大值 m。
接下来 n 行，每行两个整数 l,r，代表一次查询。
输出格式
对于每次查询输出一行，若 l,r∈[1,m]，则输出区间质数个数，否则输出 Crossing the line。
输入输出样例
输入
2 5
1 3
2 6
输出
2
Crossing the line
水题，直接上代码，按照欧拉筛的模板做就行了，如果欧拉筛不清楚走传送门https://blog.csdn.net/m0_57071296/article/details/119873446可以参考我以前写的
具体实现看代码
#include<iostream> #define N 1000001 using namespace std; int m,n,l,r ,b[N],ans[N];int a[N]={1,1}; int tot=0; int main() { cin>>n>>m;int k; for(int i=2;i<=m;i++)//这个意思是在m里面找到质数并且标记 ，质数最小是2，所以i=2 { ans[i]=ans[i-1]; if (a[i]==0)//如果没有被标记为1，就是质数。 b[++k]=i; ans[i]=k; for(int j=1;j<=k;j++)// //j小于当前所有的质数的个数 { if(i*b[j]>m)break;// 如果超出给出的范围，那么就退出循环 a[i*b[j]]=1;//用质数数依次×i，结果标记为合数（也就是标记为1）。 if(i%b[j]==0)break;//最关键的只标记一次 } } for(int i=1;i<=n;++i) { cin>>l>>r; if(l<1||r>m) cout<<"Crossing the line"; else cout<<ans[r]-ans[l-1]; cout<<endl; } }
