标签归档:筛素数

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;
}