只要用到 ≤√R 的所有素数去“打”区间 [L,R] 上的倍数，就能把所有合数都筛掉，原因在于：

任何落在 [L,R] 中的合数 N，都至少有一个不大于 √N ≤ √R 的质因子。

证明很简单：

• 若 N 是合数，则存在整数 a,b>1，使 N=a·b。
• 如果 both a>√R 且 b>√R，那么 a·b>√R·√R=R，与 N≤R 矛盾。
• 因此，a 或 b（至少一个因子）必须 ≤√R。

这意味着：

1. 我们只需先在 [2,√R] 上用普通埃拉托色尼筛出所有小素数 P。
2. 再用这些 P 去把 [L,R] 上能被它们整除的数全部标记为合数，剩下的就是质数。

不用管更大的素数，因为任何由它们构成的合数，早就被它所对应的“较小”因子给标记掉了。

下面是一份面向学生的、较为系统的解题思路梳理，包含问题分析、朴素思路的不足、核心技巧（分段筛法），以及如何在实践中一步步实现。

一、题目归纳

• 输入：多组询问，每组给定两个整数 $L,R$，满足

  $$1 \le L < R < 2^{31},\quad R - L \le 10^6.$$

• 任务：在闭区间 $[L,R]$ 内找出：

  1. 最“紧邻” 的一对相邻质数（差值最小），以及它们的差值；
  2. 最“远隔” 的一对相邻质数（差值最大），以及它们的差值；
  3. 如果区间内质数不足两枚，输出 “There are no adjacent primes.”。

• 输出格式（对每组输入）：

  • 存在相邻质数时：

    p1,p2 are closest, q1,q2 are most distant.
    

    其中 $(p1,p2)$ 差最小，$(q1,q2)$ 差最大；若并列，取区间中先出现的那对。

  • 否则：

    There are no adjacent primes.
    

二、朴素思路及其瓶颈

1. 直接判每个数是质数 对 $[L,R]$ 中的每个整数 $x$，做一次 $O(\sqrt x)$ 的 trial division 判素数，记录所有质数，再线性扫描相邻对。

   • 最坏情况下区间长度可达 $10^6$，每次判 $O(\sqrt R)\approx 2^{15}$ 级别，复杂度约 $10^6\times 10^4 = 10^{10}$ 量级，会超时。

2. 预先筛到 $R$ 用普通 Eratosthenes 筛到全区间的上限，比如 $2^{31}-1$？不现实，内存和时间都爆掉。

因此，需要对「大区间但相对较短」（长度 $\le10^6$）做高效判素，这正是**分段筛法（Segmented Sieve）**的典型应用场景。

三、分段筛法核心思想

1. 先对 $\sqrt R$ 范围内的质数做一次普通筛（上限约 $\sqrt{2^{31}}\approx 46340$）

   • 用经典 Eratosthenes 筛出所有小于等于 $\lfloor \sqrt R\rfloor$ 的质数，记为列表 smallPrimes[]。

2. 对区间 $[L,R]$ “分段”标记

   • 申请长度为 $R-L+1$ 的布尔数组 isPrimeSegment[i]（初始化都设为 true），

   • 对于 smallPrimes[k] 中的每个素数 $p$，将它在 $[L,R]$ 上的倍数都标记为合数：

     • 找到区间内第一个不小于 $L$ 的 $p$ 的倍数 $\max(p^2,\; \lceil L/p\rceil\cdot p)$，
     • 然后步长 $p$ 标记：for (j = start; j <= R; j += p) isPrimeSegment[j-L] = false;

   • 特别地，如果 $L=1$，要把 isPrimeSegment[0] 设为 false，因为 1 不是质数。

3. 筛完以后，$[L,R]$ 内剩下的 true 即为质数。

   • 依次扫描 isPrimeSegment，用一个变量 prevPrime 记住上一个遇到的质数，

   • 每遇到一个新质数 curPrime：

     1. 如果 prevPrime 有意义，就计算差值 d = curPrime - prevPrime；
     2. 检查并更新「最小差」和「最大差」对应的质数对；
     3. 令 prevPrime = curPrime 继续扫描。

4. 最后根据是否找到过一次「相邻质数」来输出对应格式。

五、复杂度与可行性

• 预处理：对 $\le 46340$ 做一次埃氏筛，$O(M \log\log M)$，其中 $M=4.6\times10^4$ 常数非常小。

• 每组查询分段筛：

  • 对每个小质数 $p$ 标记 $\approx\frac{R-L+1}{p}$ 次，

  • 综合起来大约是

    $$ \sum_{p\le\sqrt R} \frac{R-L+1}{p} \;=\;(R-L+1)\sum_{p\le\sqrt R}\frac1p \;=\;O\bigl((R-L)\log\log R\bigr). $$

  • 因为 $R-L\le10^6$，$\log\log R$ 也才数级，足够高效。

• 空间：$O(R-L+1)$ 的布尔数组，最多 $10^6$ 大小，常数可接受。

六、教学要点

1. 为什么要分段筛？ 当区间上限很大但区间长度受限时，分段筛只在我们关心的那一段做筛，避免了全域筛到 $R$ 的高昂开销。

2. 起始标记位置 start = max(p*p, ceil(L/p)*p) 的含义：

   • 如果 $p^2$ 已经小于 $L$，应该从 $\lceil L/p\rceil\cdot p$ 开始；
   • 否则从 $p^2$（埃氏筛的经典起点）开始，能够确保不漏和不重复。

3. 相邻质数差的统计 扫描时只保留「上一次遇到的质数」，每次新遇到就更新差值即可，节省了额外存储。

4. 边界与特殊情况

   • 当区间内质数数目 $<2$ 时，直接输出 “无相邻” 的提示；
   • 注意 $L$ 可能为 1，要把 1 排除掉。