<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

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

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

输入格式

每行输入两个整数 $L$ 和 $U$，其中 $L$ 和 $U$ 的差值不会超过 $10^6$。

输出格式

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

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

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

数据范围

$1 \\le L < U \\le 2^{31}-1$

输入样例：

2 17
14 17

输出样例：

2,3 are closest, 7,11 are most distant.
There are no adjacent primes.

思路

我们虽然看到$1≤l<r≤2^{31}−1$，但是$r-l\le10^6$，所以我们考虑直接筛$[l,r]$的质数。
因为一个数$n$的因子都可以转化成不超过$\sqrt{n}\le 5\times 10^4$的数的倍数，所以我们可以直接筛出$[1,5\times 10 ^ 5]$的质数，然后枚举所有质数，埃氏筛筛掉所有$[l,r]$的质数，最后模拟一下即可。

代码

#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1000010;
int l,r;
bool is_prime[N];
int primes[N],cnt;
void get_primes (int n) {
    memset (is_prime,true,sizeof (is_prime));
    is_prime[1] = false;
    cnt = 0;
    for (int i = 2;i <= n;i++) {
        if (is_prime[i]) primes[++cnt] = i;
        for (int j = 1;primes[j] * i <= n;j++) {
            is_prime[primes[j] * i] = false;
            if (i % primes[j] == 0) break;
        }
    }
}
int main () {
    while (cin >> l >> r) {
        get_primes (50000);
        memset (is_prime,true,sizeof (is_prime));
        for (int i = 1;i <= cnt;i++) {
            LL p = primes[i];
            for (LL j = max (2 * p,(l + p - 1) / p * p);j <= r;j += p) is_prime[j - l] = false;
        }
        cnt = 0;
        for (int i = 0;i <= r - l;i++) {
            if (is_prime[i] && i + l > 1) primes[++cnt] = i + l;
        }
        if (cnt < 2) puts ("There are no adjacent primes.");
        else {
            int minp = 1,maxp = 1;
            for (int i = 1;i + 1 <= cnt;i++) {
                int d = primes[i + 1] - primes[i];
                if (d < primes[minp + 1] - primes[minp]) minp = i;
                if (d > primes[maxp + 1] - primes[maxp]) maxp = i;
            }
            cout << primes[minp] << ',' << primes[minp + 1] << " are closest, " << primes[maxp] << ',' << primes[maxp + 1] << " are most distant." << endl;
        }
    }
    return 0;
}