我们发现它只是要取连续的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
#include
using namespace std;
#define manx 500000
bool s[manx];
int p[manx],num,dis[manx*2+50];
void prime(){
for(int i=0;i
for(int i=2;i*i
for(int j=2;j*i
}
}
num=0;
for(int i=2;i
}
int main(){
long long a,b;
prime();
while(cin>>a>>b){
for(int i=0;i
long long min=1000001,max=-1,l1=0,r1=0,l2=0,r2=0;
for(int i=0;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
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);
}
}