素数筛 poj 2689

素数筛

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

#define MAXN 47000

#define inf  100000000

bool z[MAXN];

int  x[MAXN];

bool y[];

int x1[];

int main()

{

    int a,b;

    for(int i=;i<=;i++) //可以从小的素数开始筛

    {

        if(!z[i])

            for(int j=i*i;j<MAXN;j+=i)

                z[j]=;

    }

    int cnt=;

    for(int i=;i<MAXN;i++) //这个范围可以筛出2147483647

        if(!z[i])

            x[cnt++]=i;

    while(scanf("%d%d",&a,&b)!=EOF)

    {

        int m1=inf,m2=-;

        int en=b-a;

        memset(y,,sizeof(y));

        if(a==)

            a++;

        for(int i=;i<cnt;i++)  //b-a<=1000000  从a开始筛

        {

            int a1,b1;

            a1=(a-)/x[i]+;

            b1=b/x[i];

            for(int j=a1;j<=b1;j++)

                if(j>)

                    y[j*x[i]-a]=;

        }

        int cnt1=;

        for(int i=;i<=b-a;i++)

            if(!y[i])

            {

                x1[cnt1++]=i+a;

            }

        int i=,j=cnt1-;

        while(x1[i]<a)

            i++;

        while(x1[j]>b&&j>=)

            j--;

        int l1,r1,l2,r2;

        for(int k=i;k+<=j;k++)

        {

            if(x1[k+]-x1[k]>m2)

            {

                m2=x1[k+]-x1[k];

                r2=x1[k+];

                l2=x1[k];

            }

            if(x1[k+]-x1[k]<m1)

            {

                m1=x1[k+]-x1[k];

                r1=x1[k+];

                l1=x1[k];

            }

        }

        if(m2==-)

            printf("There are no adjacent primes.\n");

        else

            printf("%d,%d are closest, %d,%d are most distant.\n",l1,r1,l2,r2);

    }

    return ;

}