给定两个整数L和U,你需要在闭区间[L,U]内找到距离最接近的两个相邻质数C1和C2(即C2-C1是最小的),如果存在相同距离的其他相邻质数对,则输出第一对。
同时,你还需要找到距离最远的两个相邻质数D1和D2(即D1-D2是最大的),如果存在相同距离的其他相邻质数对,则输出第一对。
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e6+5; int p[N],cnt,vis[N],ans[N],num; void pre() { for(int i=2;i<N;i++) { if(!vis[i])p[++cnt]=i; for(int j=1;p[j]<N/i;j++) { vis[i*p[j]]=1; if(i%j==0)break; } } } int main() { pre(); int l,r; while(cin>>l>>r) { memset(vis,0,sizeof vis); num=0; for(int i=1;i<=cnt;i++) { ll pr=p[i]; for(ll j=max(pr*2,(l+pr-1)/pr*pr);j<=r;j+=pr) vis[j-l]=1; } for(int i=0;i<=r-l;i++) if(!vis[i]&&i+l>=2) ans[++num]=i+l; if(num<2)puts("There are no adjacent primes."); else { int minn=0x3f3f3f3f,nx,ny; int maxx=0,xx,xy; for(int i=1;i<num;i++) { int d=ans[i+1]-ans[i]; if(d<minn)minn=d,nx=i,ny=i+1; if(d>maxx)maxx=d,xx=i,xy=i+1; } printf("%d,%d are closest, %d,%d are most distant.\n",ans[nx],ans[ny],ans[xx],ans[xy]); } } return 0; }