区间筛法

好，我们一起来看看，当想要找出很大范围内的一小段里有哪些质数时，有哪些聪明的办法。这篇文章就是来帮你搞懂“区间筛法”的。

什么是区间筛法？为什么需要它？

想象一下，你是一个探险家，在一片巨大的沙漠（范围有十万公里）里寻找古代金币。你时间有限，只想仔细搜查其中一小段100米长的沙丘。你肯定不会把整片沙漠都挖一遍，对吧？你只需要在你关心的那100米区域里，用上最高效的探测工具就行了。

在编程世界里，当我们想找一个特别大的区间内（比如从1亿到1亿零1千）有哪些质数时，情况就类似了。区间右端点 R 可能高达10亿甚至万亿，但区间长度 (R - L + 1) 可能只有几千或几万。如果使用普通的埃氏筛或线性筛法，我们得创建一个大小为 R+1 的巨型布尔数组。这就像在沙漠里盖一个仓库来存放所有沙子的信息——不仅浪费内存（可能内存不够），而且大部分数据我们根本用不上。

区间筛法（Segmented Sieve） 正是为了解决这类问题而生的。它的核心思想是：只关心你需要的那个小区域，并利用已知的、更小的质数来找出这个区域里的质数。这就像你只带一架高精度金属探测器，去搜索那片100米长的沙丘，而不会去管其他地方的沙子。

这个方法非常高效，特别适合当 R 非常大（比如大于 $10^8$），但 R - L 相对较小（比如小于 $10^6$ 或 $10^7$）的情况。

核心原理：用“小质数”清理“大区域”

为什么可以通过小质数来判断大区域里的数是不是质数呢？这基于一个非常关键的数学性质：任何一个合数（不是质数的数）都至少有一个质因子小于或等于它自己的平方根。

• 比如，合数 121 = 11 * 11，它的因子 11 正好等于它的平方根 √121 = 11。
• 合数 143 = 11 * 13，它的因子 11 小于它的平方根 √143 ≈ 11.96。
• 合数 101 是质数，它没有小于等于 √101 ≈ 10.05 的因子（被2，3，5，7检查后都不整除）。

所以，要判断区间 [L, R] 里的任意一个数 x 是不是质数，我们不需要检查所有小于 x 的数，只需要检查所有小于等于 √R 的质数就够了！因为如果 x 是合数，它的大于 √x 的因子，必定对应一个小于等于 √x 的因子，而这个因子一定小于等于 √R（因为 x <= R）。

生活中的类比：排队报数

想象一下，你要在操场上找出班级里（假设有100人）所有身高超过1.6米的同学。你不需要一个一个去测量每个人的身高。你可以先打印出全班同学的名单（这就是区间 [L, R]）。然后，你只找来一个身高为1.6米的基准人（这就是小质数 p）。你拿着这个基准人，去名单上对照：凡是身高明显比这个基准人矮的同学，就可以直接排除（相当于被小质数筛掉）。这样，你就不用去研究每个人的身高了。最后，名单上剩下的、没有被你的“基准人”排除掉的同学，就是身高超过1.6米的（相当于质数）。

区间筛法详细步骤

让我们用数字一步步来。假设我们要找出区间 [100, 120] 内所有的质数。

第一步：准备“小质数名单”

1. 确定右端点 R = 120。

2. 计算 limit = sqrt(R) = sqrt(120) ≈ 10.95，向下取整再加1（为了确保包含 sqrt 内的所有质数），limit = 11。我们用普通的埃氏筛法（或线性筛法）找出 [2, 11] 之间的所有质数。它们就是我们的“小质数名单” base_primes。

   登录后复制

   base_primes = [2, 3, 5, 7, 11]
   

第二步：为区间“铺好一张检查表”

1. 创建一个布尔数组 is_prime_in_range，长度为区间长度 R - L + 1 = 120 - 100 + 1 = 21。所有格子初始值设为 True，表示我们姑且认为区间里的每一个数都是质数。

   • 索引0对应数 L (100)
   • 索引1对应数 L+1 (101)
   • 索引20对应数 R (120)
   登录后复制

   is_prime_in_range = [True, True, True, ..., True]  // 一共21个
   

第三步：用每个“小质数”去标记合数

现在，我们拿着 base_primes 里的每个小质数 p，来标记区间 [100, 120] 里的“坏蛋”合数。

规则：对于每个质数 p，我们要找到它在区间内的第一个倍数，并且这个倍数不能是p本身（因为p是质数）。然后从那个倍数开始，每隔 p 个数就标记一个合数。

用公式找到第一个倍数 start： start = max(p * p, ((L + p - 1) // p) * p)

• p * p：为什么从 p * p 开始而不是 2 * p？因为小于 p * p 的倍数（比如 2*p, 3*p, ..., (p-1)*p）在更早的、使用更小的质数时，已经被筛过了。这样能避免重复工作。
• ((L + p - 1) // p) * p：这个公式用于找到第一个大于或等于 L 的 p 的倍数。(L + p - 1) // p 是 L 除以 p 的向上取整。乘以 p 后，就得到了那个倍数。

我们用 p = 2 来举例：

• p * p = 4
• (L + p - 1) // p * p = (100 + 2 - 1) // 2 * 2 = 101 // 2 * 2 = 50 * 2 = 100
• max(4, 100) = 100
• 所以 start = 100。
• 然后，我们标记 100（合数），102，104，...，直到 120（每次加2）。

用 p = 3 来举例：

• p * p = 9
• (100 + 3 - 1) // 3 * 3 = 102 // 3 * 3 = 34 * 3 = 102
• max(9, 102) = 102
• 所以 start = 102。
• 标记 102，105，108，111，114，117，120（每次加3）。

用 p = 5：

• p * p = 25
• (100 + 5 - 1) // 5 * 5 = 104 // 5 * 5 = 20 * 5 = 100
• max(25, 100) = 100
• 标记 100，105，110，115，120（注意，有的已经被标记过了，没关系）。

用 p = 7：

• p * p = 49
• (100 + 7 - 1) // 7 * 7 = 106 // 7 * 7 = 15 * 7 = 105
• max(49, 105) = 105
• 标记 105，112，119（每次加7）。

用 p = 11：

• p * p = 121
• (100 + 11 - 1) // 11 * 11 = 110 // 11 * 11 = 10 * 11 = 110
• max(121, 110) = 121
• start = 121，但121 > R = 120，所以这个循环根本不会开始，直接跳过。

第四步：读取检查表

经过以上所有小质数的标记后，我们的 is_prime_in_range 数组里，还有哪些位置是 True 呢？我们数一数：101, 103, 107, 109, 113。注意，100, 102, 104... 都被标记成了 False（合数）。97虽然也是质数，但它不在区间 [100, 120] 里，所以跟我们没关系。

所以最后的结果是：[101, 103, 107, 109, 113]。完美！

新手容易犯的错误

1. 忘记处理 L = 1 或 L = 0 的情况：1 不是质数，0 也不是。在开始区间筛法之前，一定要检查 L 的值。如果 L < 2，最简单的方法就是把它强制设成 2。

   登录后复制

   if (L < 2) L = 2;
   

2. start 计算错误导致漏筛或错筛：

   • 如果 start 算小了，比如你从 2p 开始而不是 p*p，会导致重复标记，不影响结果但浪费性能。
   • 如果 start 算大了，可能漏掉一些合数，这是大问题。比如，如果你从 ((L + p - 1) / p) * p 开始，但忘了考虑 p * p，那么当 L 很小，比如 L = 5，p = 3 时，start 计算为 6。但 3 * 3 = 9，而 9 才应该被标记。不过，如果 L 范围内的数都大于 p，且 p 很小，6 这个倍数已经在之前用更小的质数（2）标记过了，所以从 6 开始标记也没问题，只是多了一个 True -> False 的操作。但严格来说，从 p*p 开始是最优的。所以 max(p*p, ...) 是标准做法。

3. 数组越界：在标记时，j = start; j <= R; j += p。循环条件一定要是 j <= R，而不是 j < R。同时，标记时用 is_prime_in_range[j - L] 索引。确保 j - L 在 0 到 R - L 之间。

4. 数据类型溢出：当 R 很大（比如10亿）时，p * p 可能超过 int 能表示的范围。在C++中，务必使用 long long 类型。

   登录后复制

   long long start = max((long long)p * p, (L + p - 1) / p * p);
   

5. 空间复杂度考虑：虽然区间筛法已经很省内存了，但 is_prime_in_range 数组的大小是 R - L + 1。如果这个长度超过 10^7（一千万），内存占用可能达到10MB，在竞赛中也要注意。可以使用 bitset 或 vector<bool> 来进一步节省内存（vector<bool> 会以比特位存储）。

完整可运行代码示例

以下是详细的、带有中文注释的C++和Python代码，可以直接复制运行。

C++ 代码

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// 埃氏筛：返回 2 到 n 的所有质数
vector<int> simple_sieve(int n) {
    vector<bool> is_prime(n + 1, true);  // is_prime: 标记2到n是否为质数, 初始全部为true
    vector<int> primes;                  // primes: 存储找到的质数
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);          // 如果i是质数，加入列表
            if ((long long)i * i <= n) { // 使用long long防止i*i溢出
                for (long long j = (long long)i * i; j <= n; j += i) {
                    is_prime[j] = false; // 标记从i*i开始的i的倍数为合数
                }
            }
        }
    }
    return primes;
}

// 区间筛法：找出 [L, R] 内的所有质数（L >= 2）
vector<long long> segment_sieve(long long L, long long R) {
    if (L < 2) L = 2;                     // 处理L<2的情况
    long long limit = sqrt(R) + 1;        // limit: 右端点的平方根+1

    // 1. 先得到 sqrt(R) 以内的所有质数
    vector<int> base_primes = simple_sieve(limit); // base_primes: 小质数名单

    // 2. 标记区间内的数
    vector<bool> is_prime_in_range(R - L + 1, true); // is_prime_in_range: 区间检查表，初始全为true
    for (int p : base_primes) {                    // p: 当前小质数
        // 找到在区间内第一个能被 p 整除的数（大于等于 L）
        long long start = max((long long)p * p, (L + p - 1) / p * p); // start: 开始标记的位置
        // 从 start 开始，每隔 p 标记合数
        for (long long j = start; j <= R; j += p) {
            is_prime_in_range[j - L] = false;      // 标记j为合数
        }
    }

    // 3. 收集结果
    vector<long long> result; // result: 存储区间内的所有质数
    for (long long i = 0; i <= R - L; ++i) {
        if (is_prime_in_range[i]) {
            result.push_back(L + i); // L+i就是区间内的原数
        }
    }
    return result;
}

int main() {
    long long L, R;
    cout << "请输入区间 [L, R]（L >= 2）：";
    cin >> L >> R;
    vector<long long> primes = segment_sieve(L, R);
    cout << "区间 [" << L << ", " << R << "] 内的质数有：" << endl;
    for (long long p : primes) {
        cout << p << " ";
    }
    cout << endl;
    cout << "共 " << primes.size() << " 个" << endl;
    return 0;
}

Python 代码

import math

def simple_sieve(n: int):
    """埃氏筛，返回 2 到 n 的所有质数"""
    is_prime = [True] * (n + 1)  # is_prime: 标记2到n是否为质数, 初始全部为True
    primes = []                     # primes: 存储找到的质数
    for i in range(2, n + 1):
        if is_prime[i]:
            primes.append(i)
            if i * i <= n:
                # 标记从 i*i 开始的所有 i 的倍数为合数
                for j in range(i * i, n + 1, i):
                    is_prime[j] = False
    return primes

def segment_sieve(L: int, R: int):
    """区间筛法，返回 [L, R] 内的所有质数，L >= 2"""
    if L < 2:    # 处理L<2的情况
        L = 2
    limit = int(math.isqrt(R)) + 1   # limit: 右端点的平方根+1

    # 1. 得到 sqrt(R) 以内的质数
    base_primes = simple_sieve(limit) # base_primes: 小质数名单

    # 2. 标记区间内的合数
    size = R - L + 1                  # size: 区间长度
    is_prime_in_range = [True] * size # is_prime_in_range: 区间检查表，初始全为True
    for p in base_primes:             # p: 当前小质数
        # 找到第一个 >= L 的 p 的倍数
        start = max(p * p, ((L + p - 1) // p) * p) # start: 开始标记的位置
        # 从 start 开始，每隔 p 标记
        for j in range(start, R + 1, p):
            is_prime_in_range[j - L] = False # 标记j为合数

    # 3. 收集结果
    result = [] # result: 存储区间内的所有质数
    for i in range(size):
        if is_prime_in_range[i]:
            result.append(L + i) # L+i就是区间内的原数
    return result

def main():
    L = int(input("请输入区间左端点 L（L >= 2）："))
    R = int(input("请输入区间右端点 R："))
    primes = segment_sieve(L, R)
    print(f"区间 [{L}, {R}] 内的质数有：")
    print(' '.join(map(str, primes)))
    print(f"共 {len(primes)} 个")

if __name__ == "__main__":
    main()

总结与应用拓展

现在，当你下次再遇到“在浩瀚的数字海洋中，寻找一小片孤岛的质数”这类问题时，脑海里就会立刻浮现出区间筛法这个聪明的工具了。