這道題目坑了多久就不說了，最初看錯了題意，以為數值最大范圍在0 ~ 1000000；交上去WA了，在仔細看了下題目，原來是我太天真...數據真大啊，但是
我們發現它只是要取連續的1000000區間值，但是我們知道 2,147,483,647 開下方，如果不能被0 ~ 2,147,483,647^(1/2) 中的質因子整除，那它必然是一個
質數...所以就要先把 0 ~ 2,147,483,647^(1/2) 區間內所有的質數篩選出來，然後遍歷每個質因子，把 L ~ U 區間內所有是質因子p 的倍數刪除..也可以用一個
dis[ ] 進行標記，最後再離散化的處理也行....WA了我多回的是要注意 1 不是質數...
代碼：
#include<iostream>
#include<cstdio>
using namespace std;
#define manx 500000
bool s[manx];
int p[manx],num,dis[manx*2+50];
void prime(){
for(int i=0;i<manx;i++)
s[i]=0;
for(int i=2;i*i<manx;i++){ /// 篩選素數
if(!s[i]){
for(int j=2;j*i<manx;j++)
s[i*j]=1;
}
}
num=0;
for(int i=2;i<manx;i++)
if(!s[i]) p[num++]=i;
}
int main(){
long long a,b;
prime();
while(cin>>a>>b){
for(int i=0;i<b-a+3;i++)
dis[i]=0;
long long min=1000001,max=-1,l1=0,r1=0,l2=0,r2=0;
for(int i=0;i<num;i++){ /// 刪除是 p[] 的倍數，也就是標記一下
long long j=a/p[i];
if(j*p[i]>b) break;
if(a%p[i]) j++;
if(j==1) j++; /// 剛好可以整除得到 1 ,那麼 a 一定是素數
for( ; j*p[i]<=b; j++ ){ /// 刪除p[i]的倍數
dis[j*p[i]-a]=1;
}
}
long long g=0,left;
for(long long i=0;i<=b-a;i++){
if(!g && !dis[i]){
left=i;
if(left+a==1) continue; //// 1 不是質數哇，一定要注意，WA了好多回了
g=1; continue;
}
if(!dis[i]){
if(min>i-left){
min=i-left;
l1=left; r1=i;
}
if(max<i-left){
max=i-left;
l2=left; r2=i;
}
left=i;
}
} www.2cto.com
if(min==1000001 && max==-1) printf("There are no adjacent primes.\n");
else printf("%lld,%lld are closest, %lld,%lld are most distant.\n",l1+a,r1+a,l2+a,r2+a);
}
}
