UVA10140 Prime Distance

给定两个整数L,R(1<=L<=R<=2^{31},R-L<=10^6)L,R(1<=L<=R<=231,R−L<=106)，求闭区间 [L,R][L,R] 中相邻两个质数的差的最小值和最大值是多少，分别输出这两个质数。

首先我们发现：R-LR−L 的范围很小，我们应该要能够快速求出 L\sim RL∼R 之间的质数。

显然有推论：任意一个合数 xx 必定包含一个不超过 \sqrt xx​ 的质因子。

所以我们可以筛出 [1,\sqrt R][1,R​] 之间的所有质数，对于每个质数 pp，把 [L,R][L,R] 中能被 pp 整除的数标记为合数。最终没有被标记的数就是质数，对相邻的质数两两比较，找出差值最小和最大的即可。

#include <map>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

typedef long long LL;

#define res register int

const LL N=1e6+100;

LL v[N],p[N],tot;

LL L,R;

inline LL max(LL a,LL b){return a>b?a:b;}

inline LL min(LL a,LL b){return a<b?a:b;}

inline void primes(LL n)

{

    memset(v,0,sizeof(v)); tot=0;

    for(res i=2 ; i<=n ; i++)

    {

        if(!v[i]) v[i]=i,p[++tot]=i;

        for(res j=1 ; j<=tot ; j++)

        {

            if(p[j]>n/i || p[j]>v[i]) break;

            v[i*p[j]]=p[j];

        }

    }

}

LL a[N],cnt;

LL vis[N];

int main()

{

    primes(N);

    while(cin>>L>>R)

    {

        memset(vis,0,sizeof(vis));

        for(res i=1 ; i<=tot ; i++)

        {

            for(res j=L/p[i] ; p[i]*j<=R ; j++)

            {

            	LL x=j*p[i];

            	if(j>1 && x>=L) vis[x-L]=1;

			}

        }

        if(L==1) vis[0]=1;

        cnt=0;

        for(res i=L ; i<=R ; i++) if(!vis[i-L]) a[++cnt]=i;

        if(cnt<=1) {

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

            continue;

        }

        LL maxn(-1e9),minn(1e9),x,y;

        for(res i=1 ; i<cnt ; i++)

            if(a[i+1]-a[i]<minn) minn=a[i+1]-a[i],x=a[i],y=a[i+1];

        printf("%lld,%lld are closest, ",x,y);

        for(res i=1 ; i<cnt ; i++)

            if(a[i+1]-a[i]>maxn) maxn=a[i+1]-a[i],x=a[i],y=a[i+1];

        printf("%lld,%lld are most distant.\n",x,y);

    }

    return 0;

}

UVA10140 Prime Distance的相关教程结束。