POJ2689：Prime Distance—

http://poj.org/problem?id=2689

题目大意，给不超过int的l，r，其中r-l+1<=1000000，筛出其中的素数，并且求出相邻素数差值最大和最小的一对。

——————————————————

显然这是一道筛出l和r之间素数的裸题。

我们发现对于区间里的一个合数，其最大质因子不会超过50000（不然50000平方就大于2147483647）

秉承着正难则反的思想，筛1-50000素数，然后用一种很神奇的方法判断掉区间里的合数，统计素数即可。

判断方法：

首先我们将每个素数（记为su）平方得到t，一定是合数。

如果发现其<l。

我们就可以t=l/su*su，得到的也一定是合数。

如果此时仍然<l，我们为t+=su，得到的还是合数。

当然如果超了r那就continue；

然后对于t打标记。

然后不断地t+=su直到超r为止。

可以发现一定能够筛全合数。

简略证明：

不断地加相当于乘。

所以实际上我们在做的就是（例如su=2），就是2*2,2*3,2*4,2*5……这些全是合数。

而且因为起点是平方，所以避免了3*2这样的重复产生，所以更加的快捷。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<cmath>

#include<map>

#include<algorithm>

using namespace std;

const int INF=;

int su[]={};

bool he[]={};

int cnt=;

bool vis[]={};

void Euler(int n){

    for(int i=;i<=n;i++){

    if(he[i]==){

        cnt++;

        su[cnt]=i;

    }

    for(int j=;j<=cnt&&i*su[j]<=n;j++){

        he[su[j]*i]=;

        if(i%su[j]==)break;

    }

    }

    return;

}

int main(){

    Euler();

    int l,r;

    while(scanf("%d%d",&l,&r)!=EOF){

    memset(vis,,sizeof(vis));

    int ans=;

    for(int i=;i<=cnt&&su[i]<=sqrt(r);i++){

        //t接下来无论怎么变都是合数

        int t=su[i]*su[i];

        if(t<l)t=l/su[i]*su[i];//t太小的时候就得这样让它变大点

        if(t<l){

        if(t<=r-su[i]){

            t+=su[i];

        }else continue;

        }

        while(t<=r){

        vis[t-l]=;

        if(t==su[i])vis[t-l]=;//压缩空间

        if(t<=r-su[i])t+=su[i];

        else break;

        }

    }

    if(l==)vis[]=;

    int p=-;

    int x1,y1,x2,y2,ans1=-,ans2=INF;

    for(int i=;i<=r-l;i++){

        if(!vis[i]){

        if(p==-){p=i;continue;}

        if(ans1<i-p){ans1=i-p;x1=p+l;y1=i+l;}

        if(ans2>i-p){ans2=i-p;x2=p+l;y2=i+l;}

        p=i;

        }

    }

    if(ans1==-)cout<<"There are no adjacent primes."<<endl;

        else cout<<x2<<","<<y2<<" are closest, "<<x1<<","<<y1<<" are most distant."<<endl;

    }

    return ;

}

巴特西

POJ2689：Prime Distance——题解

最新文章

热门文章