分析

• 本题中要求求解在区间[L, R]之间相邻质数距离的最小值和最大值。

• 因为线性筛法只能从1开始筛，因此一种基本做法是将1~R中的所有质数筛出来，然后在区间[L, R]中扫描一遍即可。但是这种做法对于本题不可行，因为L、R最大为$2^{31} - 1 = 2147483647$，二十多亿的计算量，空间也会超，不可行。

• 仔细读题可以发现 $R - L \le 10 ^ 6$，我们可以考虑从这一点出发，考入如何只筛区间[L, R]，对于一个合数x，则其一定存在一个质因子p，且$p \le \sqrt n$，因此我们只需要将$1$~$\sqrt {2 ^ {31} - 1}$之间的质数筛出来，大于需要筛除1~50000之间的质数即可。

• 则对于[L, R]之间的任意一个合数x，则其必定存在一个质因子p，其值在1~50000之间且$p < x$；反之也成立。即x是合数$\iff$x存在一个小于自己的质因子。

• 因此，本题的步骤是：

（1）找出1~50000中所有的质因子；

（2）对于1~50000中的每个质数p，将[L, R]中的所有p的倍数筛掉（至少是两倍）；

（3）遍历[L, R]之间的质数，找出距离最小值和最大值。

• 现在考虑第（2）步如何处理：如何枚举[L, R]中所有p的倍数呢？我们只需要找到大于等于L的最小的p的倍数即可，该数值为 $\lceil \frac{L}{p} \rceil \times p = \lfloor \frac{L + p - 1}{p} \rfloor \times p$。另外至少要是两倍，因此需要从$max(p \times 2, \lfloor \frac{L + p - 1}{p} \rfloor \times p)$开始枚举。

• 时间复杂度：假设区间长度为$10^6$，对于每个质数p，最多有$\frac{10^6}{p}$个p的倍数，因此

$$ \frac{10^6}{2} + \frac{10^6}{3} + \frac{10^6}{5} + … = 10 ^ 6 \times (\frac{1}{2} + \frac{1}{3} + \frac{1}{5} + …) = 10^6 \times log(log(\sqrt{10^6})) $$

即时间复杂度为$O(n \times log(log(\sqrt{n})))$的。

代码

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 1000010;

int primes[N], cnt;  // 刚开始存储[1~50000]之间的质数, 然后被复用, 存储[L, R]之间的质数
int st[N];  // 也会被复用, 表示是否被筛掉

void init(int n) {

    memset(st, 0, sizeof st);
    cnt = 0;

    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] * i <= n; j++) {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}


int main() {

    int l, r;
    while (cin >> l >> r) {

        // (1) 找出1~50000中所有的质因子
        init(50000);

        // (2) 对于1~50000中的每个质数p，将[L, R]中的所有p的倍数筛掉（至少是两倍）
        memset(st, 0, sizeof st);
        for (int i = 0; i < cnt; i++) {
            LL p = primes[i];
            for (LL j = max(p * 2, (l + p - 1) / p * p); j <= r; j += p)
                st[j - l] = true;  // 代表区间[L, R]中的数据j是合数
        }

        cnt = 0;
        for (int i = 0; i <= r - l; i++)
            if (!st[i] && i + l >= 2)  // i+l = 1时，1不是质数
                primes[cnt++] = i + l;

        // (3) 遍历[L, R]之间的质数，找出距离最小值和最大值。
        if (cnt < 2) puts("There are no adjacent primes.");
        else {
            int minp = 0, maxp = 0;
            for (int i = 0 ; 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;
            }

            printf("%d,%d are closest, %d,%d are most distant.\n",
                primes[minp], primes[minp + 1],
                primes[maxp], primes[maxp + 1]);
        }
    }

    return 0;
}