题目描述

给定两个整数L和U，你需要在闭区间[L,U]内找到距离最接近的两个相邻质数C1和C2（即C2-C1是最小的），如果存在相同距离的其他相邻质数对，则输出第一对。

同时，你还需要找到距离最远的两个相邻质数D1和D2（即D1-D2是最大的），如果存在相同距离的其他相邻质数对，则输出第一对。

输入格式
每行输入两个整数L和U，其中L和U的差值不会超过1000000。

输出格式
对于每个L和U ，输出一个结果，结果占一行。

结果包括距离最近的相邻质数对和距离最远的相邻质数对。（具体格式参照样例）

如果L和U之间不存在质数对，则输出“There are no adjacent primes.”。

数据范围
1≤L<U≤2^31−1

样例

输入样例：
2 17
14 17
输出样例：
2,3 are closest, 7,11 are most distant.
There are no adjacent primes.

线性筛法求sqrt(n)

Eratosthenes筛法

时间复杂度

$O(sqrt(R)loglogsqrt(R)+(R-L)loglogR)$

参考文献

蓝书

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000010;
bool v[maxn];
int prime[maxn],cnt;

void primes(int n)
{
    memset(v,false,sizeof v);
    cnt=0;
    for(int i=2;i<=n;i++)
    {
        if(!v[i])
        {
            prime[cnt++]=i;
        }
        for(int j=0;prime[j]*i<=n;j++)
        {

            v[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
}

int main()
{
    long long l,r;
    while(cin>>l>>r)
    {
        primes(50000);
        memset(v,false,sizeof v);
        for(int i=0;i<cnt;i++)
        {
            int p=prime[i];
            for(long long j=max((l+p-1)/p*p,2ll*p);j<=r;j+=p)
            {
                v[j-l]=true;
            }
        }
        cnt=0;
        for(int i=0;i<=r-l;i++)
        {
            if(!v[i]&&i+l>1)
            {
                prime[cnt++]=i+l;
            }
        }
        if(cnt<2)
        {
            puts("There are no adjacent primes.");
        }
        else
        {
            int minn=0,maxn=0;
            for(int i=0;i+1<cnt;i++)
            {
                int d=prime[i+1]-prime[i];
                if(d<prime[minn+1]-prime[minn])minn=i;
                if(d>prime[maxn+1]-prime[maxn])maxn=i;
            }
            printf("%d,%d are closest, %d,%d are most distant.\n",prime[minn],prime[minn+1],prime[maxn],prime[maxn+1]);
        }
    }
    return 0;
}