质数距离
题目 质数距离
思路分析
找距离最近和距离最远的相邻质数对
假设所有的质数已经找出来了 那么就是做一遍双指针 用max维护prime[i+1]-prime[i]的最大值 用min维护prime[i+1]-prime[i]的最小值 记录相应最大最小的i
但问题在于 如何找到[L,U]范围内的所有质数
用筛法的话（依赖于第一个素数2 得从2开始） 得筛2~\(2^{31}-1\) 这显然不现实 然后取大于L的第一个质数作为左边界 又是一个问题
换个思路 从L到U 用试除法判断素数的话 左边界的问题解决了 但是时间复杂度为\(O(nlog\\sqrt{m})\)约等于 \(10^{10}\)(其中n为区间长度\(10^6\)，m为数字大小 \(10^9\)
很可能会超时 但也不是不能做 考试的时候能分析到这里拿个70分就差不多了
#include<bits/stdc++.h>
using namespace std;
int L,U;
int main()
{
while(cin>>L>>U){
vector<int> legal_primes;
for(int i=L;i<=U;i++){
bool is_prime=true;
if(i<2)
is_prime=false;
for(int j=2;j<=i/j;j++){
if(i%j==0){
is_prime=false;
continue;
}
}
if(is_prime)
legal_primes.push_back(i);
}
int cnt=legal_primes.size();
// cout<<cnt<<endl;
// for(auto a:legal_primes)
// cout<<a<<" ";
// cout<<endl;
if(cnt<2)
cout<<"There are no adjacent primes.";
else{
int minp=0,maxp=0;
for(int i=0;i+1<cnt;i++){
int d=legal_primes[i+1]-legal_primes[i];
if(d<legal_primes[minp+1]-legal_primes[minp])
minp=i;
if(d>legal_primes[maxp+1]-legal_primes[maxp])
maxp=i;
}
cout<<legal_primes[minp]<<","<<legal_primes[minp+1]<<" are closest, "
<< legal_primes[maxp]<<","<<legal_primes[maxp+1]<<" are most distant."<<endl;
}
}
return 0;
}
ntm 好好好 这样玩是吧
c:
代码的核心部分没有问题，可以正常工作来寻找区间内距离最近和最远的相邻质数对。但是，考虑到你的担忧关于效率问题，确实存在一些潜在的效率问题，特别是在大区间范围内。试除法的时间复杂度在最坏情况下接近 \(O(n\\sqrt{m})\)，对于非常大的 L 和 U，这可能会导致程序运行缓慢。
解决这一效率问题的一种方法是使用更高效的素数筛法，如埃拉托斯特尼筛法或更高效的筛法（如Atkin筛法），以在较大的区间内快速找出所有质数。然而，对于从 L 到 U 的区间筛法，可以采用一种被称为 "区间筛" 的变体，这需要对筛法进行一些修改以适应仅筛选一个区间内的素数，而不是从最小值开始到 U。
me:
正如前面分析的 正常的埃氏筛和线性筛都是依赖于第一个素数2工作的 要进行筛选需要从2开始进行 但是这个数据范围达到了2^31-1 从2开始显然不合适 谈谈你提到的区间筛吧
c:
区间筛（Segmented Sieve）是一种高效处理大区间内素数筛选的方法，特别适合于当你需要找到所有在较大区间 [L, U] 内的素数时使用。相比于传统的埃拉托斯特尼筛法（Eratosthenes Sieve）和线性筛法，区间筛的优势在于它不需要从最小的素数开始对整个数域进行筛选，而是直接对指定的区间进行筛选，从而节省了大量的内存和时间，尤其是当 L 很大而 U-L 相对较小的情况。
区间筛的基本思想
- 预筛选小于等于 \(\\sqrt{U}\) 的所有素数：首先使用传统的筛法（如埃拉托斯特尼筛法）找出所有小于等于 $\sqrt{U} $的素数。这一步是因为区间 [L, U] 内的任何合数都可以由小于等于 \(\\sqrt{U}\)的素数筛去。
- 筛选区间内的素数：使用上一步得到的素数列表来筛选区间 [L, U] 内的素数。具体来说，对于每一个小于等于$ \sqrt{U}$ 的素数 p，计算 p 在 [L, U] 内的最小倍数（如果 L 不是 p 的倍数，则是下一个最近的 p 的倍数），然后从这个最小倍数开始，步进为 p，标记出区间内所有 p 的倍数为合数。
区间筛的实现步骤
- 初始化：创建一个布尔数组
isPrime，大小为 U-L+1，用于标记区间 [L, U] 内的数是否为素数（初始均设为 true）。 - 筛选小于等于$ \sqrt{U} $的素数：使用传统筛法找出所有小于等于$ \sqrt{U}$的素数。
- 使用小素数筛选区间 [L, U]：对于每一个找到的素数 p，从其在区间 [L, U] 内的最小倍数开始标记出所有的倍数为合数。这里需要计算出 p 在 [L, U] 范围内的第一个倍数的位置，如果 L 是 p 的倍数，则从 L 开始；否则，从 L + (p - L % p) % p 开始。
- 收集结果：遍历
isPrime数组，所有标记为 true 的位置对应的数就是区间 [L, U] 内的素数。
通过这种方法，区间筛能够有效地筛选出大区间内的所有素数，同时显著减少所需的存储空间和运算时间，特别是对于非常大的数值范围。
好耶 新知识 emmm
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 50000; // 用于筛选 sqrt(r) 内的素数
const int M = 1000010; // 大于 r-l 的最大范围
bool st[N], isPrime[M]; // st用于筛 sqrt(r) 内的素数，isPrime用于标记区间[l, r]内的数是否为素数
int primes[N], cnt; // primes数组存放所有小于等于 sqrt(r) 的素数，cnt为计数器
// 线性筛 所有小于sqrt(r)的素数
void get_primes(int n) {
memset(st, 0, sizeof st);
cnt = 0;
for (int i = 2; i <= n; ++i) {
if (!st[i]) {
primes[cnt++] = i;
for(int j=i;j<=n;j+=i)
primes[j]=true;
}
}
}
int main()
{
int l, r;
while (~scanf("%d%d", &l, &r)) {
get_primes((int)sqrt(r) + 1);
memset(isPrime, true, sizeof isPrime);
for (int i = 0; i < cnt; ++i) {
LL p = primes[i];
LL start = max(p * 2, (l + p - 1) / p * p); // 计算在区间[l, r]内p的最小倍数
for (LL j = start; j <= r; j += p)
isPrime[j - l] = false; // 标记合数
}
// 收集区间[l, r]内的所有素数
vector<int> segmentPrimes;
for (int i = 0; i <= r - l; ++i)
if (isPrime[i] && i + l > 1) // 排除1
segmentPrimes.push_back(i + l);
if (segmentPrimes.size() < 2)
printf("There are no adjacent primes.\n");
else {
// 寻找距离最近和最远的素数对
int minp = 0, maxp = 0;
for (int i = 0; i + 1 < segmentPrimes.size(); ++i) {
int d = segmentPrimes[i + 1] - segmentPrimes[i];
if (d < segmentPrimes[minp + 1] - segmentPrimes[minp])
minp = i;
if (d > segmentPrimes[maxp + 1] - segmentPrimes[maxp])
maxp = i;
}
printf("%d,%d are closest, %d,%d are most distant.\n",
segmentPrimes[minp], segmentPrimes[minp + 1],
segmentPrimes[maxp], segmentPrimes[maxp + 1]);
}
}
return 0;
}
💬 评论