题意

给你一个区间，问你这个区间里面，最近的连续素数对和最远的连续素数对

思路

我们知道一个合数$x=pqx\; =\; pq$，$pp$和$qq$里面肯定存在一个 $\le \sqrt{x}\backslash leq\; \backslash sqrt\{x\}$。 通过这个思路，我们知道筛去区间$[L,R][L,\; R]$的合数，只需要$[2,\sqrt{R}][2,\; \backslash sqrt\{R\}]$的素数就可以

代码

/**
 *    author: andif
 *    created: 26.07.2023 23:08:17
**/
#include<bits/stdc++.h>
using namespace std;

#define de(x) cerr << #x << " = " << x << endl
#define dd(x) cerr << #x << " = " << x << " "
#define rep(i, a, b) for(int i = a; i < b; ++i)
#define per(i, a, b) for(int i = a; i > b; --i)
#define mt(a, b) memset(a, b, sizeof(a))
#define sz(a) (int)a.size()
#define fi first
#define se second
#define qc ios_base::sync_with_stdio(0);cin.tie(0)
#define eb emplace_back
#define all(a) a.begin(), a.end()
using ll = long long;
using db = double;
using pii = pair<int, int>;
using pdd = pair<db, db>;
using pll = pair<ll, ll>;
using vi = vector<int>;
const db eps = 1e-9;
const int n = 46343;

int main() {
    qc;
    int t; cin >> t;
    vector<pii> a(t);
    rep(i, 0, t) cin >> a[i].fi >> a[i].se;
    vi is_prime(n, 1);
    is_prime[1] = 0;
    // vector<vi> primes(t);
    vector<vi> is_p(t);
    rep(i, 0, t) {
        is_p[i].resize(a[i].se - a[i].fi + 1, 1);
        if (a[i].fi == 1) is_p[i][0] = 0;
    }
    rep(i, 2, n) {
        if (is_prime[i]) {
            for (int j = 2 * i; j < n; j += i) {
                is_prime[j] = 0;
            }
        }
    }
    rep(i, 2, n) {
        if (is_prime[i]) {
            rep(j, 0, t) {
                auto [l, r] = a[j];
                ll h = l % i ? (1ll * l + i - 1) / i : l / i;
                ll k = max(h, 2ll) * i;
                for (;k <= r; k += i) {
                    // if (!j) dd(j), dd(k), de(k - l);
                    is_p[j][k - l] = 0;
                }
            }
        }
    }
    rep(i, 0, t) {
        auto [l, r] = a[i];
        int cnt = 0;
        rep(j, 0, r - l + 1) {
            if (is_p[i][j]) cnt++;
        }
        if (cnt < 2) {
            cout << "There are no adjacent primes." << '\n';
            continue;
        }
        int p = -1;
        int d = numeric_limits<int>::max();
        int dd = -1; 
        int c1 = -1, c2 = -1;
        int c5 = -1, c6 = -1;
        rep(j, 0, r - l + 1) {
            if (is_p[i][j]) {
                int c = j + l;
                if (~p) {
                    int cd = c - p;
                    if (cd < d) {
                        d = cd;
                        c1 = p, c2 = c;
                    }
                    if (cd > dd) {
                        dd = cd;
                        c5 = p, c6 = c;
                    }
                }
                p = j + l;
            }
        }
        cout << c1 << "," << c2 << " are closest, ";
        cout << c5 << "," << c6 << " are most distant." << '\n';
    }
    return 0;
}