定两个整数 L,R , 求闭区间 [L,R] 中相邻两个质数差值最小的数对与差值最大的数对。
当存在多个时,输出靠前的素数对。
筛 1e6
每个素数,在区间里标记倍数
#include<iostream> #include <algorithm> #include <cstring> using namespace std; const int M=1e6+10; #define int long long int P[M],fac[M],tot; int b[M]; int bin[M],B; void init(int top){ int i,j; for(i=2;i<=top;i++) P[i]=1; P[0]=P[1]=0; for(i=2;i<=top;i++){ if(P[i]==0) continue; fac[++tot]=i; for(j=i*2;j<=top;j+=i) P[j]=0; } } int L,R; void sov(){ int i,j; memset(b,0,sizeof b); if(L==1){ b[0]=1; } for(i=1;i<=tot;i++){ for(j=L/fac[i];j<=R/fac[i];j++) if(j>1) b[j*fac[i]-L]=1; } B=0; for(i=L;i<=R;i++) if(b[i-L]==0) bin[++B]=i; int t1=2147483647,t2=0; int x1,y1,x2,y2; for(i=1;i<B;i++){ int t =bin[i+1]-bin[i]; if(t1>t){ x1=bin[i],y1=bin[i+1],t1=t; } if(t2<t){ x2=bin[i],y2=bin[i+1],t2=t; } } if(t2==0) printf("There are no adjacent primes.\n"); else printf("%d,%d are closest, %d,%d are most distant.\n", x1,y1,x2,y2); } signed main(){ init(6e4); while(cin>>L>>R) sov(); }