形式化题目

给定整数 $L, R$，记闭区间 $[L, R]$ 内的质数按升序为

要求找出相邻两项之差最小的一对，以及差最大的一对，即求

当极值被多对同时取得时，输出下标 $i$ 更小（即数值更靠前）的那一对。若 $k < 2$，则不存在相邻质数对。

约束：$1 \leqslant L < R < 2^{31}$，$R - L \leqslant 10^6$，多组数据直到输入结束。

正解

思路

1. 朴素做法：逐个试除

最直接的写法是枚举 $[L, R]$ 中的每个数 $n$，用 $2 \sim \sqrt{n}$ 试除判断它是不是质数：

1
2
3for n in range(L, R + 1):
    if all(n % d for d in range(2, int(n ** 0.5) + 1)):  # 不可行
        primes.append(n)

它的代价是 $O\big((R-L)\sqrt{R}\big)$。代入最坏情况 $R-L = 10^6$、$\sqrt{R} \approx 46341$，约为 $4.6 \times 10^{10}$ 次取模，必然超时。问题出在同一个 $n$ 被反复地从零开始试除，前面所有数试除得到的信息全被丢弃了。

2. 为什么不能直接筛到 $R$

换一个思路：用埃氏筛一次性筛出 $[2, R]$ 的质数表，再批量取相邻质数。但这里 $R$ 可以接近 $2^{31}$，布尔数组需要 $2^{31}$ 字节 $\approx 2\ \text{GB}$，远超 128 MB 的内存限制，连开都开不出来。

这就是本题的核心矛盾：数值上界极大（$2^{31}$），但区间长度极小（$10^6$）。

3. 关键观察：合数的小质因子一定很小

设 $n \leqslant R$ 是合数，把它分解为 $n = a \times b$（$2 \leqslant a \leqslant b$），则

也就是说：$[L, R]$ 中任何一个合数，都一定能被某个不超过 $46341$ 的质数整除。 反过来，只要把 $[2, 46341]$ 内的质数全部取来，用它们去"划掉"$[L, R]$ 中的倍数，剩下的就全是质数——而 $[2, 46341]$ 的筛只需要 46 KB。

于是算法分成两层：

内存由"区间长度"而非"数值上界"决定，矛盾就此化解。

4. 分段筛的划除细节

开一个长度为 $R - L + 1$ 的布尔数组 is_prime，下标 $i$ 代表数字 $L + i$，初值全部置 1（先假定都是质数）。对预处理的每个小质数 $p$：

1. 若 $p^2 > R$，说明 $p$ 已经大到无法在区间内构成合数（最小的候选是 $p^2$ 本身），后面的 $p$ 只会更大，直接 break。
2. 找出第一个要划掉的倍数位置：

两个下界各有道理：$p^2$ 以下的部分早就被更小的质数划过了，不必重划；$\lceil L/p \rceil \cdot p$ 则是把起点抬进区间 $[L, R]$。取 $\max$ 同时满足两者——当 $p \geqslant L$ 时它就是 $p^2$，避免把质数 $p$ 自己误划。 3. 从 start 起，每 $p$ 个位置划一次，即把 is_prime[start-L::p] 整段置 0。

最后单独处理 $L = 1$ 的情形：数字 1 既不是质数也不是合数，但按上面的流程它永远不会被任何 $p$ 划掉，需要手工把下标 0 置 0。做完这些，is_prime 中为 1 的位置对应的数字就是 $[L, R]$ 的全部质数。

5. 样例推演

以样例 2 17 为例，$R = 17 < 46341$，小质数表为 $2, 3, 5, 7, 11, 13, \dots$，逐个划除：

得到质数序列 $2, 3, 5, 7, 11, 13, 17$，相邻差依次为

最小差 $1$ 对应 $(2, 3)$，最大差 $4$ 第一次出现在 $(7, 11)$，与样例输出一致。

再看第二个样例 14 17：区间内质数只有 $17$ 一个，$k = 1 < 2$，输出 There are no adjacent primes.，同样吻合。

6. 取最值对：并列取靠前

primes 已经升序，相邻差就是 primes[i+1] - primes[i]。Python 的 max / min 在遇到多个极值时返回第一个达到极值的元素，这恰好就是题面要求的"输出靠前的素数对"，不需要额外写判等逻辑：

1
2choose = max if want_max else min
return choose(zip(primes, primes[1:]), key=lambda pair: pair[1] - pair[0])

以 2 17 为例，zip(primes, primes[1:]) 给出 $(2,3),(3,5),(5,7),(7,11),(11,13),(13,17)$，键分别为 $1,2,2,4,2,4$；max 返回第一个键为 4 的 $(7,11)$，min 返回第一个键为 1 的 $(2,3)$。

最后按 a,b are closest, c,d are most distant. 的格式输出即可。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 22:41
# update_at: 2026-09-30 22:41

import sys

LIMIT = 46341          # floor(sqrt(2**31 - 1))，筛出这段小数就能覆盖 [L,R] 的全部合数
CLOSEST = "are closest, "
DISTANT = "are most distant."
NONE = "There are no adjacent primes."


def small_primes(n: int) -> list[int]:
    """返回 [2, n] 内的所有质数，作为区间筛的“试探除数”集合。"""
    sieve = bytearray([1]) * (n + 1)      # 1 表示暂时认为它是质数
    sieve[0:2] = b"\x00\x00"
    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i]:
            sieve[i * i :: i] = bytearray(len(sieve[i * i :: i]))  # 质数 i 的倍数全是合数
    return [i for i in range(2, n + 1) if sieve[i]]


def segment_primes(L: int, R: int, base: list[int]) -> list[int]:
    """返回闭区间 [L, R] 内的所有质数，按升序排列。

    下标 i 对应数字 L+i，只筛这一段，内存取决于区间长度而不是 R 的大小。
    """
    width = R - L + 1
    is_prime = bytearray([1]) * width       # 先全部假定为质数，再被小质数划掉
    for p in base:
        if p * p > R:
            break
        # 从 >= L 的第一个 p 的倍数开始划；L 较小时下界不能低于 p 本身
        start = max(p * p, (L + p - 1) // p * p)
        is_prime[start - L :: p] = bytearray(len(range(start, R + 1, p)))
    if L == 1:                              # 1 既不是质数也不是合数，单独处理
        is_prime[0] = 0
    return [L + i for i in range(width) if is_prime[i]]


def best_pair(primes: list[int], want_max: bool) -> tuple[int, int]:
    """取相邻质数差最大（want_max=True）或最小的那一对，并列时取更靠前的。

    max/min 返回第一个达到极值的元素，正好满足“输出靠前的素数对”。
    """
    choose = max if want_max else min
    return choose(zip(primes, primes[1:]), key=lambda pair: pair[1] - pair[0])


def solve() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    base = small_primes(LIMIT)

    out: list[str] = []
    for i in range(0, len(data), 2):
        L, R = data[i], data[i + 1]
        primes = segment_primes(L, R, base)
        if len(primes) < 2:                 # 少于两个质数就没有“相邻质数对”
            out.append(NONE)
            continue
        lo_a, lo_b = best_pair(primes, want_max=False)
        hi_a, hi_b = best_pair(primes, want_max=True)
        out.append(f"{lo_a},{lo_b} {CLOSEST}{hi_a},{hi_b} {DISTANT}")

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 23:02
 * update_at: 2026-10-05 23:02
 */

// 分段筛（区间筛）模板题：R 可达 2^31，但 R-L <= 10^6。
// 先筛出 [2, sqrt(R)] 内的小质数，再用它们划掉 [L,R] 中的合数，
// 剩下的就是区间内的全部质数，线性扫描相邻差取最小/最大即可。

#include <cstdio>
#include <cstring>

typedef long long ll;

const int BASE = 46341;      // sqrt(2^31) < 46341，小质数筛到这个上界就够
const int MAXN = 1000005;    // 区间长度 R-L+1 最大为 10^6+1

bool is_comp[BASE + 1];      // 埃氏筛的标记数组：is_comp[i]=1 表示 i 是合数
ll base_primes[5000];        // [2, 46341] 内的小质数约 4800 个（π(46341)=4792）
ll cnt_base;                 // 小质数个数

bool seg_comp[MAXN];         // seg_comp[i]=1 表示数字 L+i 是合数

// 埃氏筛预处理 [2, BASE] 内的小质数
void sieve_base() {
    memset(is_comp, 0, sizeof(is_comp));
    cnt_base = 0;
    for (ll i = 2; i <= BASE; i++) {
        if (!is_comp[i]) {
            base_primes[++cnt_base] = i; // 下标从 1 开始存
            for (ll j = i * i; j <= BASE; j += i) is_comp[j] = 1;
        }
    }
}

// 用小质数表对 [L, R] 做分段筛，划掉区间内所有合数
void segment_sieve(ll L, ll R) {
    // 初始时假定区间内每个数都是质数候选（下标 i 对应数字 L+i）
    memset(seg_comp, 0, sizeof(seg_comp));
    for (ll k = 1; k <= cnt_base; k++) {
        ll p = base_primes[k];
        if (p * p > R) break; // p^2 > R 时 p 无法在区间内构成任何合数，后面只会更大

        // 第一个要划掉的倍数：不小于 L 的最小 p 倍数，但不能低于 p^2
        // （p^2 以下的倍数已被更小的质数划过；p >= L 时取 p^2 可避免误划质数 p 自己）
        ll start = (L + p - 1) / p * p;
        if (start < p * p) start = p * p;

        for (ll j = start; j <= R; j += p) seg_comp[j - L] = 1;
    }

    // 数字 1 不是质数，但它不会被任何小质数划掉，需要单独排除
    if (L == 1) seg_comp[0] = 1;
}

// 对区间内剩下的质数线性扫描，输出相邻差最小/最大的数对
void solve(ll L, ll R) {
    segment_sieve(L, R);

    // prev 记录上一个质数；diff 用 -1 区分"还没有质数对"
    ll prev = 0, diff_min = -1, diff_max = -1;
    ll ans_a1 = 0, ans_b1 = 0, ans_a2 = 0, ans_b2 = 0;

    for (ll i = L; i <= R; i++) {
        if (seg_comp[i - L]) continue; // 合数跳过
        if (prev == 0) { prev = i; continue; }
        ll diff = i - prev;
        if (diff_min == -1 || diff < diff_min) {
            // 并列时取更靠前的：只在严格更小时更新
            diff_min = diff;
            ans_a1 = prev; ans_b1 = i;
        }
        if (diff_max == -1 || diff > diff_max) {
            // 并列时取更靠前的：只在严格更大时更新
            diff_max = diff;
            ans_a2 = prev; ans_b2 = i;
        }
        prev = i;
    }

    if (diff_min == -1)
        printf("There are no adjacent primes.\n");
    else
        printf("%lld,%lld are closest, %lld,%lld are most distant.\n",
               ans_a1, ans_b1, ans_a2, ans_b2);
}

int main() {
    sieve_base();
    ll L, R;
    while (scanf("%lld %lld", &L, &R) == 2) {
        solve(L, R);
    }
    return 0;
}

复杂度

• 时间复杂度：预处理部分 $O(\sqrt{R} \log\log R)$，只做一次；之后每组数据的分段筛为 $O\big((R-L+1)\log\log R\big)$。代入 $R-L \leqslant 10^6$、$\sqrt{R} \approx 46341$，远优于逐个试除的 $O\big((R-L)\sqrt{R}\big)$，二者在 $R-L = 10^6$ 时相差约 $4.6 \times 10^4$ 倍。
• 空间复杂度：$O(\sqrt{R} + (R - L + 1))$，即 46 KB 的小质数表加上最大 1 MB 的区间标记数组，与直接筛到 $R$ 所需的 $O(R) \approx 2\ \text{GB}$ 相比是决定性的差异。

图示解析

下图给出 $L = 10^9$、$R = 10^9 + 20$ 这一小段区间的分段筛全流程。上排是 $[2, 46341]$ 预处理得到的小质数，下排是区间内每个位置的标记状态；箭头表示某质数正在划除它的倍数。

flowchart LR
    A["预处理：埃氏筛<br/>[2, 46341]"] --> B["小质数表 base<br/>2,3,5,7,11,..."]
    B --> C{"对每个 p：<br/>p*p > R ?"}
    C -- 是 --> F["收集 is_prime 中<br/>仍为 1 的下标"]
    C -- 否 --> D["start = max(p*p, ceil(L/p)*p)"]
    D --> E["is_prime[start-L::p] = 0<br/>按步长 p 整段划除"]
    E --> C
    F --> G["primes = [L+i ...]<br/>升序质数序列"]
    G --> H{"len(primes) >= 2 ?"}
    H -- 否 --> I["There are no adjacent primes."]
    H -- 是 --> J["min(zip(p, p[1:]), key=差)<br/>max(zip(p, p[1:]), key=差)"]
    J --> K["a,b are closest,<br/>c,d are most distant."]

下表展示这一段的筛除过程（· 表示仍被标记为质数候选，× 表示已被划掉），可以清楚看到区间长度只有 21，全部工作都在这一小段内完成：

划除结束后只剩 $1000000007$ 与 $1000000009$ 两个质数，它们就是这段区间里唯一的相邻质数对，因此既是最近的也是……实际上是唯一的一对，差为 2。这组数据正好出现在本题的测试点 1000000000 1001000000 中——该点的答案 $1000000007,1000000009$ 正是最小的那一对。

总结

本题是"分段筛（区间筛）"的模板题，它的全部内容可以浓缩成一句观察：

若 $n \leqslant R$ 是合数，则 $n$ 必有不超过 $\sqrt{R}$ 的质因子。

由此把一次不可能的"筛到 $R$"拆成两次可行的筛：一次在极小的 $[2, \sqrt{R}]$ 上建立质数表，一次在极小的 $[L, R]$ 上标记合数。当题面同时给出巨大的数值上界和极小的区间长度时，这几乎总是标准出路——内存和时间的开销都应该绑定在区间长度上，而不是数值本身上。

实现上还有两个 Python 细节值得记住：用 bytearray 的扩展切片赋值（is_prime[start-L::p] = 0）完成整段划除，循环体在 C 层执行，比手写 for 快两个数量级；取"并列最靠前"的一对时直接依赖 min/max 返回首个极值的语义，不必额外比较下标。