题目链接：点击查看
题目大意：给出一段闭区间[l,r]，求区间内相邻距离最大的素数对和相邻距离最小的素数对，题目保证r-l<=1e6，1<=l<=r<=
题目分析：因为我们要求区间[l,r]内的最近和最远素数对，肯定要求出这段区间内的所有素数，l和r最大都能到1e9，并且其区间也到了1e6，暴力打表然后暴力遍历肯定是不行的，我们可以换一个思路，先在sqrt(1e9)的范围内打个素数表，这个用欧拉线性筛就能搞定，然后正难则反，我们最终要求的是所有素数，那么我们只需要将区间内的合数筛掉即可，合数的定义就是除了被1和自身整除外还有其他的质数所整除的数，那么我们可以在跑出来的素数表中遍历每一个素数，将该素数能在区间内组成的所有合数都筛掉，最后至多用1e6的时间复杂度跑一遍就能跑出最大值和最小值了
对了，为了方便处理，我在更新vis区间的时候将[l,r]区间向左偏移至原点，这样就变成了[0,1e6]，方便处理，最后在输出答案时记得将答案都加上左区间即可
代码实现很清晰，欧拉线性筛也是从以前做的题目中直接复制的板子，更多的看注释吧，上代码：
#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> using namespace std; typedef long long LL; const int inf=0x3f3f3f3f; const int N=1e6+100; bool book[N]; int cnt=0; int pri[N]; bool vis[N]; void P()//欧拉筛 { for(int i=2;i<N;i++) { if(!book[i]) pri[cnt++]=i; for(int j=0;j<cnt&&pri[j]*i<N;j++) { book[pri[j]*i]=true; if(i%pri[j]==0) break; } } } int main() { // freopen("input.txt","r",stdin); P();//预处理打个素数表 LL l,r; while(scanf("%lld%lld",&l,&r)!=EOF) { memset(vis,false,sizeof(vis)); for(int i=0;i<cnt;i++) { LL a=(l+pri[i]-1)/pri[i]; LL b=r/pri[i]; for(LL j=max(a,2LL);j<=b;j++)//筛掉[l,r]内因子含有pri[i]的合数 vis[pri[i]*j-l]=true; } if(l==1)//注意1不是素数，所以需要筛掉，记得特判一下 vis[0]=true; int mark=-1; int x1,y1;//mmax int x2,y2;//mmin int mmax=-inf; int mmin=inf; for(int i=0;i<=r-l;i++) { if(vis[i])//若当前的数为合数，则直接跳过 continue; if(mark==-1)//若当前为区间内的第一个素数，不做处理 { mark=i; continue; } if(i-mark>mmax)//更新最大值 { mmax=i-mark; x1=mark; y1=i; } if(i-mark<mmin)//更新最小值 { mmin=i-mark; x2=mark; y2=i; } mark=i; } if(mmin==inf)//若连最小值或最大值都没法更新，说明区间内的素数少于2个，直接输出 printf("There are no adjacent primes.\n"); else//否则输出答案 printf("%lld,%lld are closest, %lld,%lld are most distant.\n",x2+l,y2+l,x1+l,y1+l);//答案记得加上左区间 } return 0; }
