POJ 2689 (素數的二次篩選)

poj 2689 Prime Distance （素數篩選的經典應用）

題意：給出一個區間，長度<=1000 000；求其中素數相鄰素數之間的差最小的和最大的；

算法：素數篩選

其中區間的數可能較大，是以如果用試除法的話，顯然不行的；

用篩選法，首先第一次篩選出從1到47000之間的素數；第二次篩選時，利用第一次篩

選出來的素數，判斷L到U區間範圍内的數是否是素數；

因為範圍是1<=L< U<=2,147,483,647,而U-L<=1000 000;是以我們可以設定一個1000000

以内的數組，用res[i-L]的值為0或者1來表示是否是素數；

核心算法是第二次的篩選，其中j=begin*prime[i]表示的是在A，B區間中prime[i]的第一個倍數；依次篩選；

/*************
* POJ 2689
*************/

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int SIZE = 50000;

long long L, U;
int yes[SIZE];
long long prim[SIZE];
int k=0;
int adp[1001000];

void getPrim()
{
    memset(yes,0,sizeof(yes));
    for(long long i=2;i<SIZE;i++)
        if(!yes[i])
        {
            prim[k++]=i;
            for(long long j=i*i;j<SIZE;j+=i)
                yes[j]=1;
        }
}

int main()
{
    long long pre;
    long long maxV, u1, v1;
    long long minV, u2, v2;
    int flag;

    getPrim();
    while(cin>>L>>U)
    {
        if(L<=1) L=2;
        
        //二次篩選過程
        memset(adp,0,sizeof(adp));
        for(int i=0;i<k&&prim[i]*prim[i]<=U;i++)
        {
            long long beg=L/prim[i]+(L%prim[i]>0);
            if(beg==1) beg++;
            for(long long j=beg*prim[i];j<=U;j+=prim[i])  //調整j，使得 L<=j<=U
                adp[j-L]=1;
        }

        maxV=-2*SIZE;
        minV=2*SIZE;
        flag=0;
        for(long long i=L;i<=U;i++)
        {
            if(!adp[i-L])
            {
                flag++;
                if(flag>1)
                {
                    int temp=i-pre;
                    if(temp>maxV) {maxV=temp; u1=pre; v1=i;}
                    if(temp<minV) {minV=temp; u2=pre; v2=i;}
                }
                pre=i;
            }
        }

        if(flag>1)
            cout<<u2<<","<<v2<<" are closest, "<<u1<<","<<v1<<" are most distant.\n";
        else
            cout<<"There are no adjacent primes.\n";
    }

    return 0;
}

/*

1 2
2146483648 2147483647
2147483047 2147483647


There are no adjacent primes.
2146483811,2146483813 are closest, 2146841093,2146841273 are most distant.
2147483053,2147483059 are closest, 2147483179,2147483237 are most distant.
*/