POJ 2689 -Prime Distance（区间筛素数）

题目链接：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;
}