题意:求L到R之间的素数距离最小的两个,和距离最大的两个,如果存在几个,则取第一个。(1=<L<R<=2^32)
思路:1、先预处理1到50000的素数(50000^2>2^32).存入prime[50000]中
2、for(i=0;prime[i]*prime[i]<=R;i++)
{
k=L/prime[i];
j=k*prime[i];
if(k<=1)
j=prime[i]+prime[i]; (L<=prime[i]时,如prime[0]=2,L=2;则k=1,j=2,而2是素数故不能筛去,L=1时,k=0,j=0,也不符合)
for(;j<=R;j+=prime[i])
if(j-L>=0)
isprime[j-L]=true;
}
3、代码
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <cmath> using namespace std; #define LL __int64 #define CL(a,b) memset(a,b,sizeof(a)) #define INF 0xfffffff const int M(50000); bool is[M],isprime[2000010]; LL prime[M]; void init() { int i,j; CL(is,false); is[0]=is[1]=true; for(i=2;i*i<M;i++) if(!is[i]) { for(j=i+i;j<M;j+=i) is[j]=true; } for(i=0,j=0;i<M;i++) if(!is[i]) prime[j++]=i; // printf("%d\n",prime[j-1]); } void solve(LL L,LL R) { LL i; LL j,k,minm,maxm; LL x,y,xx,yy,pre; CL(isprime,false); if(L==1) isprime[0]=true; for(i=0;prime[i]*prime[i]<=R;i++) { k=L/prime[i]; j=k*prime[i]; if(k<=1) j=prime[i]+prime[i]; for(;j<=R;j+=prime[i]) if(j-L>=0) isprime[j-L]=true; } minm=INF; maxm=0; pre=-1; x=y=xx=yy=-1; for(i=L;i<=R;i++) if(!isprime[i-L]) { // printf("%d ",i); if(pre!=-1) { if(i-pre>maxm) { maxm=i-pre; x=pre;y=i; } if(i-pre<minm) { minm=i-pre; xx=pre;yy=i; } } pre=i; } // printf("\n"); if(x!=-1) printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.\n",xx,yy,x,y); else printf("There are no adjacent primes.\n"); } int main() { LL L,R; init(); while(scanf("%I64d%I64d",&L,&R)!=EOF) { solve(L,R); } }