质数距离

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

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

输入格式

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

输出格式

对于每个 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.

解法

思路1：

​ 暴力筛出[1,\(2^{31}\)]内的所有质数，然后开gap数组存每相邻两个数的距离，但是很显然这么做空间是不允许的

思路2：

​ 根据定理1可得，对于[0,\(2^{31}\)]的范围，我们只需要筛[1,\(\sqrt{2^{31}}\)]即最大筛到1e5内的质数即可，再用这1e5范围内的质数筛去完整的[1,\(2^{31}\)]内所有合数即可，完成空间优化。

img

​ 很关键的一点，pri数组存的时候，需要用到一个偏移量（离散化思想），在用到的时候再加回来，做到不爆内存空间(在y总的视频中只是一笔带过，最开始弄得我百思不得其解)。

​ 34行的(p + l - 1) / p * p是什么意思呢？这是j的起点公式，代表p在区间[l,u]内的第一个能整除p的数。

a7821e925a358735

AC代码：

#include "iostream"
#include "cstring"

using namespace std;
typedef long long ll;

const int N = 1e6 + 10;

int pri[N];
bool st[N];
int cnt;

void ola(int n) {
    memset(pri, 0, sizeof pri);
    memset(st, false, sizeof st);//因为题目需要循环读入，所以每一次都需要清空数组
    cnt = 0;
    st[1] = true;
    for (int i = 2; i <= n; i++) {
        if (!st[i]) pri[++cnt] = i;
        for (int j = 1; i * pri[j] <= n; j++) {
            st[i * pri[j]] = true;
            if (i % pri[j] == 0)break;
        }
    }
}

int main() {
    int l, u;
     while (scanf("%d %d\n",&l,&u)==2) {
        ola(50010);//欧拉筛，筛掉前一部分的质数
        memset(st, false, sizeof st);//下面代码需要复用st数组，所以清空一次
        for (int i = 1; i <= cnt; i++) {
            ll p = pri[i];
            for (ll j = max(p << 1, (p + l - 1) / p * p); j <= u; j += p)
                st[j - l] = true;  //l作为偏移量，后面会把它加回来
        }
        cnt = 0;    //因为最后要的质数范围为[l,u],所以重置下标，pri从更新过后的st开始判，只存[l,u]内的质数
        for (int i = 0; i <= u - l; i++)
            if (!st[i] && i + l >= 2)
                pri[++cnt] = i + l; //加回偏移量
        if (cnt < 2) {
            //[l,u]内的质数数量不到一对
            puts("There are no adjacent primes.");
        } else {
            //在pri数组中查找最远/近的质数对
            int minp = 1, maxp = 1;
            for (int i = 1; i <= cnt - 1; i++) {
                int d = pri[i + 1] - pri[i];
                if (d < pri[minp + 1] - pri[minp]) minp = i;
                if (d > pri[maxp + 1] - pri[maxp]) maxp = i;
            }
            printf("%d,%d are closest, %d,%d are most distant.\n", pri[minp], pri[minp + 1], pri[maxp], pri[maxp + 1]);
        }
    }
    return 0;
}