1619：【例 1】Prime Distance

题目描述

给定两个整数 $L,R$，求闭区间 $[L,R]$ 中相邻两个质数差值最小的数对与差值最大的数对。当存在多个时，输出靠前的素数对。

输入格式

多组数据。每行两个数 $L,R$。

输出格式

对于每组数据，如果区间内存在至少两个质数，则输出两行：

• 第一行：最小差值素数对 are closest, 最大差值素数对 are most distant.
• 第二行：如果区间内质数少于两个，输出 There are no adjacent primes.

具体格式见样例。

样例

样例输入 #1

2 17
14 17

样例输出 #1

2,3 are closest, 7,11 are most distant.
There are no adjacent primes.

样例解释 #1

第一组数据：$L=2, R=17$，区间内的质数有：$2,3,5,7,11,13,17$。

• 相邻质数差值：
  • $2$ 和 $3$ 差 $1$
  • $3$ 和 $5$ 差 $2$
  • $5$ 和 $7$ 差 $2$
  • $7$ 和 $11$ 差 $4$
  • $11$ 和 $13$ 差 $2$
  • $13$ 和 $17$ 差 $4$
• 最小差值为 $1$，对应的质数对是 $(2,3)$。
• 最大差值为 $4$，对应的质数对是 $(7,11)$（因为 $(13,17)$ 差值也是 $4$，但 $(7,11)$ 靠前）。
• 输出：2,3 are closest, 7,11 are most distant.

第二组数据：$L=14, R=17$，区间内的质数只有 $17$（$14,15,16$ 不是质数），所以少于两个质数，输出 There are no adjacent primes.

数据范围

对于全部数据：

• $1 \le L < R < 2^{31}$
• $R - L \le 10^6$

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：本题需要高效地找出区间 $[L,R]$ 内的所有质数。由于 $R$ 可能很大（接近 $2^{31}$），不能直接筛到 $R$。但区间长度不超过 $10^6$，因此可以使用区间筛法（Segmented Sieve）：

1. 先用线性筛或埃氏筛筛出 $\sqrt{R}$ 以内的所有质数（因为 $R \le 2^{31}$，$\sqrt{R} \le 46341$）。
2. 然后用这些质数去标记区间 $[L,R]$ 内的合数。
3. 最后遍历 $[L,R]$ 收集所有质数，并计算相邻质数的差值。

注意点：

• $L$ 可能为 $1$，但 $1$ 不是质数。
• 需要使用 long long 类型，因为中间计算可能会超出 int 范围。
• 多组数据输入，直到文件结束。
• 输出格式要严格符合样例，注意标点符号和空格。