UVA10140 Prime Distance
给定两个整数L,R(1<=L<=R<=2^{31},R-L<=10^6)L,R(1<=L<=R<=231,R−L<=106),求闭区间 [L,R][L,R] 中相邻两个质数的差的最小值和最大值是多少,分别输出这两个质数。
-
首先我们发现:R-LR−L 的范围很小,我们应该要能够快速求出 Lsim RL∼R 之间的质数。
显然有推论:任意一个合数 xx 必定包含一个不超过 sqrt xx
所以我们可以筛出 [1,sqrt R][1,R
#include <map> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> using namespace std; typedef long long LL; #define res register int const LL N=1e6+100; LL v[N],p[N],tot; LL L,R; inline LL max(LL a,LL b){return a>b?a:b;} inline LL min(LL a,LL b){return a<b?a:b;} inline void primes(LL n) { memset(v,0,sizeof(v)); tot=0; for(res i=2 ; i<=n ; i++) { if(!v[i]) v[i]=i,p[++tot]=i; for(res j=1 ; j<=tot ; j++) { if(p[j]>n/i || p[j]>v[i]) break; v[i*p[j]]=p[j]; } } } LL a[N],cnt; LL vis[N]; int main() { primes(N); while(cin>>L>>R) { memset(vis,0,sizeof(vis)); for(res i=1 ; i<=tot ; i++) { for(res j=L/p[i] ; p[i]*j<=R ; j++) { LL x=j*p[i]; if(j>1 && x>=L) vis[x-L]=1; } } if(L==1) vis[0]=1; cnt=0; for(res i=L ; i<=R ; i++) if(!vis[i-L]) a[++cnt]=i; if(cnt<=1) { puts("There are no adjacent primes."); continue; } LL maxn(-1e9),minn(1e9),x,y; for(res i=1 ; i<cnt ; i++) if(a[i+1]-a[i]<minn) minn=a[i+1]-a[i],x=a[i],y=a[i+1]; printf("%lld,%lld are closest, ",x,y); for(res i=1 ; i<cnt ; i++) if(a[i+1]-a[i]>maxn) maxn=a[i+1]-a[i],x=a[i],y=a[i+1]; printf("%lld,%lld are most distant. ",x,y); } return 0; }