---
title: "质数距离"
created: 2025-11-28
tags:
  - 算法
---

# 质数距离

## 题目 [质数距离](https://www.acwing.com/problem/content/198/)

![[image-d5a1cba1.png]]

## 思路分析

找距离最近和距离最远的相邻质数对

假设所有的质数已经找出来了 那么就是做一遍双指针 用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分就差不多了

```cpp
#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 好好好 这样玩是吧

![[image-f9b17481.png]]

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 相对较小的情况。

**区间筛的基本思想**

1. **预筛选小于等于 $\sqrt{U}$ 的所有素数**：首先使用传统的筛法（如埃拉托斯特尼筛法）找出所有小于等于
   $\sqrt{U} $的素数。这一步是因为区间 [L, U] 内的任何合数都可以由小于等于 $\sqrt{U}$的素数筛去。
2. **筛选区间内的素数**：使用上一步得到的素数列表来筛选区间 [L, U] 内的素数。具体来说，对于每一个小于等于$
   \sqrt{U}$ 的素数 p，计算 p 在 [L, U] 内的最小倍数（如果 L 不是 p 的倍数，则是下一个最近的 p 的倍数），然后从这个最小倍数开始，步进为
   p，标记出区间内所有 p 的倍数为合数。

**区间筛的实现步骤**

1. **初始化**：创建一个布尔数组 `isPrime`，大小为 U-L+1，用于标记区间 [L,
   U] 内的数是否为素数（初始均设为 true）。
2. **筛选小于等于$ \sqrt{U} $的素数**：使用传统筛法找出所有小于等于$ \sqrt{U}$的素数。
3. **使用小素数筛选区间 [L, U]**：对于每一个找到的素数 p，从其在区间 [L, U] 内的最小倍数开始标记出所有的倍数为合数。这里需要计算出
   p 在 [L, U] 范围内的第一个倍数的位置，如果 L 是 p 的倍数，则从 L 开始；否则，从 L + (p - L % p) % p 开始。
4. **收集结果**：遍历 `isPrime` 数组，所有标记为 true 的位置对应的数就是区间
   [L, U] 内的素数。

通过这种方法，区间筛能够有效地筛选出大区间内的所有素数，同时显著减少所需的存储空间和运算时间，特别是对于非常大的数值范围。

好耶 新知识 emmm

## 代码实现

```cpp
#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;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[筛素数|筛素数]] 🏠 [[00-刷题理模型]] ➡️ [[阶乘分解|阶乘分解]]