Prime Distance
2021/5/5 18:25:17
本文主要是介绍Prime Distance,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
题目大意
给定两个整数\(L\)和\(U\),你需要在闭区间\([L,U]\)内找到距离最接近的两个相邻质数\(C_1\)和\(C_2\)(即\(C_2−C_1\)是最小的),如果存在相同距离的其他相邻质数对,则输出第一对。
同时,你还需要找到距离最远的两个相邻质数\(D_1\)和\(D_2\)(即\(D_1−D_2\)是最大的),如果存在相同距离的其他相邻质数对,则输出第一对。
思路
性质
- 性质1:若一个数是合数那必然存在两个因子\(d\)和\(\frac{n}{d}\),假设\(d\leq \frac{n}{d}\),则\(d\leq \sqrt{n}\),即\(n\)必然存在一个小于\(\sqrt{n}\)的因子。
分析
对于朴素的做法我们不难想出,打表筛除\(1\)到\(2^{31}-1\)之间的所有质数,然后对于每一个区间\([L,U]\)只需从头到尾遍历一遍即可。
但是这样必定会\(TLE\),所以我们需要挖掘出某些性质对其进行优化。而借助线性筛的原理,我们可以知道每一个合数都可以被其最小的质因子筛除。再根据上面的性质我们可知对于小于\(2^{31}-1\)的最大合数也必然存在一个小于\(\sqrt{2^{31}-1}\)的质因子。
步骤
- 筛出\(1\)到\(2^{31}-1\)的所有质数。
- 对于每一个区间\([L,U]\)使用筛出的\(1\)到\(2^{31}-1\)的所有质数进行二次筛除。
- 遍历区间\([L,U]\)找出答案。
注意事项
题目范围较大,会爆\(int\),我们需要开\(long long\)来存储。
代码
typedef long long LL; const int N = 1000010; int primes[N], cnt; LL l, r; bool st[N]; void init(int n) // 线性筛 { for (int i = 2; i <= n; i ++ ) { if (!st[i]) primes[cnt ++ ] = i; for (int j = 0; primes[j] * i <= n; i ++ ) { st[primes[j] * i] = true; if (i % primes[j] == 0) break; } } } int main() { init(N - 1); while (cin >> l >> r) { memset(st, 0, sizeof st); // 重复使用st数组 for (int i = 0; i < cnt; i ++ ) { LL t = (l + primes[i] - 1) / primes[i]; for (LL j = max(t, (LL)2); (LL)primes[i] * j <= r; j ++ ) st[(LL)primes[i] * j - l] = true; // 将l~r的下标映射到0~r-l } vector<int> q; for (LL i = l; i <= r; i ++ ) if (!st[i - l] && i != 1) // 1既不是质数也不是合数 q.push_back(i); if (q.size() <= 1) { puts("There are no adjacent primes."); continue; } int maxl, maxr, maxres = -1; int minl, minr, minres = 0x3f3f3f3f; for (int i = 0; i < q.size() - 1; i ++ ) { if (q[i + 1] - q[i] < minres) { minres = q[i + 1] - q[i]; minl = q[i], minr = q[i + 1]; } if (q[i + 1] - q[i] > maxres) { maxres = q[i + 1] - q[i]; maxl = q[i], maxr = q[i + 1]; } } printf("%d,%d are closest, %d,%d are most distant.\n", minl, minr, maxl, maxr); } return 0; }
这篇关于Prime Distance的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain