题意：给出一个区间[L,U]，找出区间里相邻的距离最近的两个素数和距离最远的两个素数。
用素数筛选法。
所有小于U的数，如果是合数，必定是某个因子(2到sqrt(U)间的素数)的倍数。
由于sqrt(U)最大也只有2^16，所以我们可以用素数筛选法，先预处理出2~2^16之间的素数，然后再用这些素数筛选出L~U之间的素数。
接着就好办了。
有几个要注意的是：
1:L为1的情况，可以通过令L=2或者标记isp[0]=false。
2:建议用long long，否则很容易在过程中超int范围，导致数组越界RE。。。
#include <iostream>
#include <cstdio>
#include <string.h> using namespace std;
const int maxn=(<<)+;
const int range=+;
bool isprime[maxn]; //标记2~2^16之间的素数
bool isp[range]; //标记L~U之间的素数，下标从0开始，对应L。
int prime[maxn]; //存储2~2^16之间的素数 int idx;
long long L,U; void init(){
idx=;
memset(isprime,true,sizeof(isprime));
for(int i=;i<maxn;i++){
if(isprime[i]){
prime[idx++]=i;
for(int j=*i;j<maxn;j+=i)
isprime[j]=false;
}
}
}
int main()
{
init();
while(scanf("%I64d%I64d",&L,&U)!=EOF){
memset(isp,true,sizeof(isp));
if(L==)
isp[]=false; //忽略L为1了，导致测试样例1 2的时候，输出结果是1和2最近，1和2最远。
//筛选出L~U之间的素数
for(int i=;i<idx;i++){
int p=prime[i];
/*
这里我RE了好几次，原因如下：
1.j一开始定义成int型，导致j*p有可能超出int范围，变成负数，这样就使得j*p-L<0。
2.L一定要设成long long型，因为l+p-1可能会超int，变成负数。。。
*/
//这里的j表示的是p的倍数，j=(L+p-1)/p表示的是第一个大于等于L的倍数
for(long long j=(L+p-)/p;j*p<=U;j++){
if(j>){
isp[j*p-L]=false;
}
}
}
int mina,minb,mindis=,maxa,maxb,maxdis=;
int a,b;
bool first=true;
for(int i=;i<=U-L;i++){
if(isp[i]){
if(!first){
b=i;
if(b-a<mindis){
mina=a;
minb=b;
mindis=b-a;
}
if(b-a>maxdis){
maxa=a;
maxb=b;
maxdis=b-a;
}
a=b;
}
else{
first=false;
a=i;
}
}
}
if(!maxdis){
printf("There are no adjacent primes.\n");
}
else{
//注意：这里输出时long long格式，因为L是long long型
printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.\n",mina+L,minb+L,maxa+L,maxb+L);
}
}
return ;
}
