质数距离

质数距离

给定两个整数 L 和 U,你需要在闭区间 [L,U] 内找到距离最接近的两个相邻质数 C1 和 C2(即 C2−C1 是最小的),如果存在相同距离的其他相邻质数对,则输出第一对。

同时,你还需要找到距离最远的两个相邻质数 D1 和 D2(即 D1−D2 是最大的),如果存在相同距离的其他相邻质数对,则输出第一对。

输入格式

每行输入两个整数 L 和 U,其中 L 和 U 的差值不会超过 10^6。

输出格式

对于每个 L 和 U,输出一个结果,结果占一行。

结果包括距离最近的相邻质数对和距离最远的相邻质数对。(具体格式参照样例)

如果 L 和 U 之间不存在质数对,则输出 There are no adjacent primes.

数据范围

1≤ L< U ≤ 2^31 -1

输入样例:

1
2
2 17
14 17

输出样例:

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

解法

思路1:

​ 暴力筛出[1,\(2^{31}\)]内的所有质数,然后开gap数组存每相邻两个数的距离,但是很显然这么做空间是不允许的

思路2:

​ 根据定理1可得,对于[0,\(2^{31}\)]的范围,我们只需要筛[1,\(\sqrt{2^{31}}\)]即最大筛到1e5内的质数即可,再用这1e5范围内的质数筛去完整的[1,\(2^{31}\)]内所有合数即可,完成空间优化。

img

​ 很关键的一点,pri数组存的时候,需要用到一个偏移量(离散化思想),在用到的时候再加回来,做到不爆内存空间(在y总的视频中只是一笔带过,最开始弄得我百思不得其解)。

​ 34行的(p + l - 1) / p * p是什么意思呢?这是j的起点公式,代表p在区间[l,u]内的第一个能整除p的数。

img

AC代码:

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
#include "iostream"
#include "cstring"

using namespace std;
typedef long long ll;

const int N = 1e6 + 10;

int pri[N];
bool st[N];
int cnt;

void ola(int n) {
memset(pri, 0, sizeof pri);
memset(st, false, sizeof st);//因为题目需要循环读入,所以每一次都需要清空数组
cnt = 0;
st[1] = true;
for (int i = 2; i <= n; i++) {
if (!st[i]) pri[++cnt] = i;
for (int j = 1; i * pri[j] <= n; j++) {
st[i * pri[j]] = true;
if (i % pri[j] == 0)break;
}
}
}

int main() {
int l, u;
while (scanf("%d %d\n",&l,&u)==2) {
ola(50010);//欧拉筛,筛掉前一部分的质数
memset(st, false, sizeof st);//下面代码需要复用st数组,所以清空一次
for (int i = 1; i <= cnt; i++) {
ll p = pri[i];
for (ll j = max(p << 1, (p + l - 1) / p * p); j <= u; j += p)
st[j - l] = true; //l作为偏移量,后面会把它加回来
}
cnt = 0; //因为最后要的质数范围为[l,u],所以重置下标,pri从更新过后的st开始判,只存[l,u]内的质数
for (int i = 0; i <= u - l; i++)
if (!st[i] && i + l >= 2)
pri[++cnt] = i + l; //加回偏移量
if (cnt < 2) {
//[l,u]内的质数数量不到一对
puts("There are no adjacent primes.");
} else {
//在pri数组中查找最远/近的质数对
int minp = 1, maxp = 1;
for (int i = 1; i <= cnt - 1; i++) {
int d = pri[i + 1] - pri[i];
if (d < pri[minp + 1] - pri[minp]) minp = i;
if (d > pri[maxp + 1] - pri[maxp]) maxp = i;
}
printf("%d,%d are closest, %d,%d are most distant.\n", pri[minp], pri[minp + 1], pri[maxp], pri[maxp + 1]);
}
}
return 0;
}

质数距离
http://example.com/2022/06/04/质数距离/
作者
Charry
发布于
2022年6月4日
许可协议