题目链接:POJ-2689
大致题意:给出 L,U (1<=L<U<=2147483647,U-L<=10^6),找出区间[L,U]中相邻两个质数的差最大是多少,最小是多少。
思路:关键是求出[L,U]内的所有质数,然后一趟比较即可得出结果。线性筛法和Eratosthenes筛法都可求出1~N内的所有质数,而这里U值上界可达2^31,所以即使用线筛也会超时(限制1s,大约是10^7次计算)。但注意到U-L只有10^6,考虑到每个合数都存在一个不超过n^0.5的质因子,我们求出[2,U^0.5]内的所有质数,对其中每个质数p,把[L,U]内能被p整除的数剔除,剩下的就是[L,U]的质数了。
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MAX_N 1000005
int prime1[MAX_N];
ll prime2[MAX_N];
int m;
int v[MAX_N];
void primes(int n) {
memset(v,0,sizeof(v));
memset(prime1,0,sizeof(prime1));
m=0;
for(int i=2; i<=n; i++) {
if(v[i]==0) {
v[i]=i;
prime1[++m]=i;
}
for(int j=1; j<=m; j++) {
if(v[i]<prime1[j]||i>n/prime1[j]) {
break;
}
v[i*prime1[j]]=prime1[j];
}
}
}
int main() {
ll L, U;
primes(sqrt(2147483647)); //预处理
while(cin>>L>>U) {
memset(v,0,sizeof(v));
memset(prime2,0,sizeof(prime2));
int n=0;
for(int i=1; i<=m; i++) {
if(prime1[i]>sqrt(U)) break;
for(ll j=L/prime1[i]; j<=U/prime1[i]; j++) {
if(prime1[i]*j>=L&&j>1) //要注意的地方
v[prime1[i]*j-L]=1;
}
}
if(L==1) v[1-L]=1; //要注意的地方
for(ll i=L; i<=U; i++) {
if(!v[i-L]) {
prime2[++n]=i;
}
}
ll maxn=0;
ll minn=2147483647;
ll a,b,c,d;
for(int i=1; i<=n-1; i++) {
if(maxn<prime2[i+1]-prime2[i]) {
maxn=prime2[i+1]-prime2[i];
a=prime2[i];
b=prime2[i+1];
}
if(minn>prime2[i+1]-prime2[i]) {
minn=prime2[i+1]-prime2[i];
c=prime2[i];
d=prime2[i+1];
}
}
if(n<2)
printf("There are no adjacent primes.\n");
else
printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.\n",c,d,a,b);
}
return 0;
}