质数距离
给定两个整数 $L$ 和 $U$，你需要在闭区间 $[L,U]$ 内找到距离最接近的两个相邻质数 $C_1$ 和 $C_2$（即 $C_2−C_1$ 是最小的），如果存在相同距离的其他相邻质数对，则输出第一对。
同时，你还需要找到距离最远的两个相邻质数 $D_1$ 和 $D_2$（即 $D_1−D_2$ 是最大的），如果存在相同距离的其他相邻质数对，则输出第一对。
输入格式
每行输入两质数距离个整数 $L$ 和 $U$，其中 $L$ 和 $U$ 的差值不会超过 ${10}^6$。
输出格式
对于每个 $L$ 和 $U$，输出一个结果，结果占一行。
结果包括距离最近的相邻质数对和距离最远的相邻质数对。（具体格式参照样例）
如果 $L$ 和 $U$ 之间不存在质数对，则输出 There are no adjacent primes. 。
数据范围
$1 \leq L < U \leq 2^{31}-1$
输入样例：
2 17 14 17
输出样例：
2,3 are closest, 7,11 are most distant. There are no adjacent primes.
解题思路
很容易想到先把所有的质数筛出来，对于每次询问遍历一遍区间范围内的质数就能够找到答案。但区间右端点最大可以取到${10}^9$，因此不可能把所有的质数给筛出来。
所有就容易想到说把区间$[L, R]$的质数筛出来，但目前筛质数的算法都是从$2$开始筛的，因此这种做法也行不通。
本质就是找到区间$[L, R]$中的质数，现在质数不好找就看看能不能把所有的合数找出来。对于每个合数$x$都必然存在一个因子$d \leq \sqrt{x}$，这就启示我们可以先把所有小于$\sqrt{2^{31}-1}$的质数筛出来，然后枚举这些质数$p$，把$[L, R]$内$p$的倍数（$2$倍以上，不可以是$1$倍否则就把质数$p$筛掉了）都筛掉。对于$[L, R]$内的合数$x$，由于必然存在一个不超过$\sqrt{x}$的质因子$p$，因此当枚举到$p$时，由于$p \mid x$因此$x$会被筛掉。需要注意的是$p$要满足$p < x$，即要满足$x$至少是$p$的$2$倍。
其中，大于等于$L$的最小的$p$的倍数是$\left\lceil {\frac{L}{p}} \right\rceil \times p$（补充，小于等于$L$的最大的$p$的倍数是$\left\lfloor {\frac{L}{p}} \right\rfloor \times p$）。
时间复杂度的计算，在$[L, R]$中，$p$的倍数最多有$\frac{{10}^6}{p}$个，因此一共需要筛$\frac{{10}^6}{2} + \frac{{10}^6}{3} + \frac{{10}^6}{5} + \frac{{10}^6}{7} + \ldots + \frac{{10}^6}{\sqrt{2^{31}-1}} \approx {10}^6 \cdot \log{\log{(2^{31}-1)}} = O(n \cdot \log{\log{m}})$。时间复杂度的计算与埃式筛法很类似。
AC代码如下：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 6 const int N = 1e6 + 10; 7 8 int primes[N], cnt; 9 bool vis[N], st[N]; 10 11 void get_prime(int n) { 12 for (int i = 2; i <= n; i++) { 13 if (!vis[i]) primes[cnt++] = i; 14 for (int j = 0; primes[j] <= n / i; j++) { 15 vis[primes[j] * i] = true; 16 if (i % primes[j] == 0) break; 17 } 18 } 19 } 20 21 int main() { 22 get_prime(47000); // sqrt(2^31 - 1) < 47000 23 int l, r; 24 while (~scanf("%d %d", &l, &r)) { 25 memset(st, 0, sizeof(st)); 26 for (int i = 0; i < cnt; i++) { 27 LL p = primes[i]; // 把[l, r]中p的数筛掉 28 LL t = max(2 * p, (l + p - 1) / p * p); // 大于等于l的最小的p的倍数（至少2倍） 29 while (t <= r) { 30 st[t - l] = true; // 由于t很大，因此减去一个偏移量，映射到10^6内 31 t += p; 32 } 33 } 34 vector<int> p; 35 for (int i = 0; i <= r - l; i++) { // 找到[l, r]内的所有质数 36 if (i + l >= 2 && !st[i]) p.push_back(i + l); 37 } 38 if (p.size() < 2) { 39 printf("There are no adjacent primes.\n"); 40 } 41 else { 42 int a = 0, b = 0; 43 for (int i = 0; i + 1 < p.size(); i++) { 44 if (p[i + 1] - p[i] < p[a + 1] - p[a]) a = i; 45 if (p[i + 1] - p[i] > p[b + 1] - p[b]) b = i; 46 } 47 printf("%d,%d are closest, %d,%d are most distant.\n", p[a], p[a + 1], p[b], p[b + 1]); 48 } 49 } 50 51 return 0; 52 }
解题思路
AcWing 196. 质数距离（算法提高课）：https://www.acwing.com/video/681/
原文链接: https://www.cnblogs.com/onlyblues/p/17062706.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/313394
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
