题解 | Prime Distance

引理：对于一个合数 $n$ ，一定有一个不超过 $\sqrt{n}$ 的质因数。
注意到 $R-L<=10^6$ 所以只需要预处理出素数，对所有的素数标记它在 $[L,R]$ 之间的倍数，之后扫一遍只要没有被标记的就一定是素数。直接存入数组判断相邻的素数即可。
复杂度是 $O(\sqrt n*\log n)$

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

#define N 2000100
#define ll long long 
#define inf 2147483647
int l, r, p[N], m, f[N];
bool vis[N];

int main() {
    int cnt = 0;
    for(int i = 2; i < 50000; ++i) {
        if(!vis[i]) p[++cnt] = i;
        for(int j = 1; j <= cnt && p[j] * i < 50000; ++j) {
            vis[i * p[j]] = 1;
            if(i % p[j] == 0) break;
        }
    }
    while(~scanf("%d%d", &l, &r)) {
        memset(vis, 0, sizeof(vis));
        if(l == 1) vis[0] = 1;
        for(int i = 1; i <= cnt; ++i) {
            for(int j = l / p[i]; j <= r / p[i]; ++j) {
                if(j > 1) vis[p[i] * j - l] = 1;
            }
        }
        m = 0;
        for(int i = l; i <= r; ++i) {
            if(!vis[i - l]) f[++m] = i;
            if(i == r) break;
        }
        int mx = 0, mn = inf, x_1 = 0, x_2 = 0, y_1 = 0, y_2 = 0;
        for(int i = 2; i <= m; ++i) {
            if(f[i] - f[i - 1] > mx) {
                mx = f[i] - f[i - 1];
                x_1 = f[i - 1], y_1 = f[i]; 
            }
            if(f[i] - f[i - 1] < mn) {
                mn = f[i] - f[i - 1];
                x_2 = f[i - 1], y_2 = f[i];
            }
        }
        if(!mx) puts("There are no adjacent primes.");
        else cout << x_2 << ',' << y_2 << " are closest, " << x_1 << ',' << y_1 << " are most distant.\n";
    }
    return 0;
}