原题链接
更好的阅读体验

题目描述

给定两个整数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.

数学性质(素数筛+离散化)

这道题目很明显是和素数也就是质数有关.题目让我们求出$[l,r]$之中的素数,那么我们很显然是需要素数筛,问题是这道题目中$[l,r]$特别大,我们无法求出$[1,r]$中的素数,但是我们发现任何一个合数n,肯定会包括一个不超过$\sqrt{n}$的素数.

通过上面这个非常有用的性质,我们就可以只需要枚举出2~$\sqrt{r}$ 之间的所有质数.既然如此的话,我们对于每一个质数p而言,我们就标记i*p为合数.$(\frac{L}{p} \le i \le \frac{r}{p})$ 这里一定要切记p不可以为1,要特判的,书上没有写!还好样例感人

找出来$[l,r]$区间内的质数后,我们面临的问题就是如何标记,因为我们总不能开一个$[1,r]$长度的数组标记吧,这里我们就需要用到离散化,具体可以看我代码中操作.

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#define ll long long
const int N=1e5+1000,M=1e6+10;
ll prime[N],a[N];
int p[M];
int zs(int n)//判定质数
{
    memset(prime,0,sizeof(prime));
    memset(a,0,sizeof(a));
    for(int i=2;i<=n;i++)
    {
        if (!prime[i])
            a[++a[0]]=i;
        for(int j=i;j<=n/i;j++)
            prime[i*j]=1;
    }
}
int main()
{
    int l,r;
    while(cin>>l>>r)
    {
        zs(sqrt(r));
        memset(p,0,sizeof(p));
        if (l==1)//1要特判啊
            p[0]=1;
        for(int i=1;i<=a[0];i++)
        {
            for(int j=ceil(l/a[i]);j<=floor(r/a[i]);j++)//celi为向上取整,floor为向下取整.
                if (j!=1)
                    p[a[i]*j-l]=1;//统一减去l
        }
        int as=0,max_ans=0,min_ans=1e9;
        pair<int,int> ans_a,ans_b;
        for(int i=l;i<=r;i++)
            if (!p[i-l])
            {
                if (as)
                {
                    if (max_ans<i-as)
                    {
                        ans_a.first=as;
                        ans_a.second=i;
                        max_ans=i-as;
                    }
                    if (min_ans>i-as)
                    {
                        ans_b.first=as;
                        ans_b.second=i;
                        min_ans=i-as;
                    }
                }
                as=i;
            }
        if (max_ans==0 && min_ans==1e9)
            printf("There are no adjacent primes.\n");//没有素数
        else
            printf("%d,%d are closest, %d,%d are most distant.\n",ans_b.first,ans_b.second,ans_a.first,ans_a.second);
    }
}