题目大意
给定两个数L和U，要求你求出在区间[L, U] 内所有素数中，相邻两个素数差值最小的两个素数C1和C2以及相邻两个素数差值最大的两个素数D1和D2，并且L-U<1,000,000
题解
由于1<=L< U<=2,147,483,647，直接筛肯定超时，但是题目说L-U<1,000,000,我们可以先筛选出sqrt(2147483647)（约等于46340）内的素数即可，然后再用这些素数把区间[L,U]内的合数筛选掉，最后就可以枚举答案了~~~
代码：
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define MAXN 50005
#define INF 1000005
int prime[MAXN];
bool com[MAXN],f[INF];
int main(void)
{
int L,U,cnt=0;
memset(com,false,sizeof(com));
com[0]=true;
com[1]=true;
for(int i=2; i<MAXN; i++)
{
if(!com[i])
prime[cnt++]=i;
for(int j=0; j<cnt&&i*prime[j]<=MAXN; ++j)
{
com[i*prime[j]]=true;
if(i%prime[j]==0) break;
}
}
while(cin>>L>>U)
{
memset(f,false,sizeof(f));
for(int i=0; i<cnt; i++)
{
int l=(L-1)/prime[i]+1,r=U/prime[i];
for(int j=l; j<=r; j++)
if(j>1)
f[j*prime[i]-L]=true;
}
int mins=INF,maxs=-INF,pre=-1,p,q,a,b;
for(int i=0; i<=U-L; i++)
if(!f[i])
{
if(pre!=-1)
{
if(i-pre+1>maxs)
{
maxs=i-pre+1;
p=pre+L;
q=i+L;
}
if(i-pre+1<mins)
{
mins=i-pre+1;
a=pre+L;
b=i+L;
}
}
if(L+i!=1) pre=i;
}
if(maxs<0) printf("There are no adjacent primes.\n");
else
printf("%d,%d are closest, %d,%d are most distant.\n",a,b,p,q);
}
return 0;
}