ZJNU 1223 - 素数距离——高级

因为最大可以达到int极限

明显直接筛选不可能完成

所以从其因子入手

因为任何不是素数的数都有除了1与其自身之外的因子

因此，我们筛出2^(31/2)≈46350之内的所有素数，以其作为因子再将题目给定区间内的所有不是素数的数标记排除

然后将素数存放在prnum这个vector集合中便于调用

在排除阶段，可以用

l=((L+prnum[i]-1)/prnum[i])*prnum[i]

计算出区间内的第一个是prnum[i]的倍数的数

注意，如果计算出来的使其本身，取倍数

再用

r=R/prnum[i]*prnum[i]

计算出最后一个是prnum[i]的倍数的数

符合条件时，从l到r，每次加prnum[i]，标记出所有以prnum[i]为因子的数

因为无法直接开数组标记到大数

但又因为R-L≤1000000

所以可以对位置进行转换

标记时取-L+1，取出时取-1+L

最后将区间内的素数取出放在ans这个vector集合内，对答案进行判断即可

（注意特殊情况的判断）

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<ll> prnum,ans;

bool prim[],ar[];

int main(){

    ll L,R,i,j,cnt,l,r,mxdis,mndis,mxn1,mxn2,mnn1,mnn2,d;

    scanf("%lld%lld",&L,&R);

    memset(prim,true,sizeof prim);

    prim[]=prim[]=false;

    for(i=;i<=;i++)

        if(prim[i])

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

                prim[j]=false;//埃氏筛法

    prnum.push_back();

    for(i=;i<=;i+=)

        if(prim[i])

            prnum.push_back(i);//将素数放置在prnum内

    cnt=prnum.size();

    memset(ar,true,sizeof ar);

    if(L==)

        ar[]=false;

    for(i=;i<cnt;i++){

        l=((L+prnum[i]-)/prnum[i])*prnum[i];

        if(l==prnum[i])//如果计算得出的l恰好为第i个素数本身，跳过它，取其倍数

            l+=l;

        if(l>R)

            continue;

        r=R/prnum[i]*prnum[i];

        for(j=l;j<=r;j+=prnum[i])

            ar[j-L+]=false;//标记

    }

    for(i=;i<=R-L+;i++)

        if(ar[i])

            ans.push_back(i-+L);//将指定区间内的所有素数提出

    cnt=ans.size();

    if(cnt<)

        puts("There are no adjacent primes.");

    else{

        mndis=mxdis=ans[]-ans[];

        mxn1=mnn1=ans[];

        mxn2=mnn2=ans[];

        for(i=;i<cnt;i++){

            d=ans[i]-ans[i-];

            if(d>mxdis){

                mxdis=d;

                mxn1=ans[i-];

                mxn2=ans[i];

            }

            if(d<mndis){

                mndis=d;

                mnn1=ans[i-];

                mnn2=ans[i];

            }

        }

        printf("%lld,%lld are closest, %lld,%lld are most distant.\n",mnn1,mnn2,mxn1,mxn2);

    }

    return ;

}