题解 | #Prime Distance#

【Prime Distance】

要找到$LL$​​​​到​​​​之间的所有素数，仅需用$\sqrt{ma{x}_R}=46340\backslash sqrt\; \{max\_R\}=46340$​​​​以内的素数进行筛选就足够了。

又因为$\sum (R-L)\le 10^6\backslash sum\; (R-L)\backslash le\; 10^6$​​​​，因此可以用埃氏筛在$O(n\log \log n)O(n\backslash log\backslash log\; n)$​的时间复杂度内筛出$[L,R][L,R]$​​内的质数。

注意：直接用memset会T掉。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 46340 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;

int prime[N], vis[N], total;
int p[M];

void Prime() {
    for (int i = 2; i <= N - 10; i++) {
        if (!vis[i]) prime[++total] = i;
        for (int j = 1; j <= total && prime[j] * i <= N - 10; j++) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}

int T, L, R;
signed main() {
    Prime();
    scanf("%lld", &T);
    while (T--) {
        scanf("%lld%lld", &L, &R);

        for (int i = 1; i <= total && prime[i] <= R; i++) {
            int w = (L + prime[i] - 1) / prime[i];
            for (int j = max(2LL, w); prime[i] * j <= R; j++)
                p[prime[i] * j - L] = 1;
        }

        vector<int> vec;  // 存储区间内的质数
        for (int i = max(2LL, L); i <= R; i++) { // 特判一下1
            if (!p[i - L]) vec.push_back(i);
            p[i - L] = 0;
        }

        if (vec.size() <= 1) {
            printf("There are no adjacent primes.\n");
        } else {
            pair<int, int> minn = {inf, -1};
            pair<int, int> maxn = {-inf, -1};
            for (int i = 0; i < vec.size() - 1; i++) {
                if (vec[i + 1] - vec[i] > maxn.first) {
                    maxn.first = vec[i + 1] - vec[i];
                    maxn.second = i;
                }
                if (vec[i + 1] - vec[i] < minn.first) {
                    minn.first = vec[i + 1] - vec[i];
                    minn.second = i;
                }
            }
            printf("%lld,%lld are closest, %lld,%lld are most distant.\n",
                   vec[minn.second], vec[minn.second + 1], vec[maxn.second],
                   vec[maxn.second + 1]);
        }
    }
    return 0;
}