素数筛法 - CSP-J | C++ & Algorithm 编程研习社

用筛子筛出质数——素数筛法详解

素数筛法是一种高效的算法，能快速找出一段范围内（比如从 2 到 100 万）的所有质数。它的名字很形象：像用筛子筛沙子一样，把合数全部筛掉，剩下的就是质数。原本一个一个判断每个数是不是质数，速度很慢（比如判断 100 万个数，每个数都要试除，复杂度很高），而素数筛法只需要一次遍历标记，就能把所有质数找出来，是编程竞赛（CSP-J）中的基本功。

1. 什么是埃氏筛法（Eratosthenes 筛法）

这个算法由古希腊数学家埃拉托斯特尼提出。假设我们有一排从 2 到 N 的数字卡片：

2  3  4  5  6  7  8  9  10  11  12  ...  N

我们按以下步骤“划掉”合数：

从最小的质数 2 开始，把 2 的倍数（4, 6, 8, 10, …）全部划掉（标记为合数）。
找到下一个没有被划掉的数 3，把 3 的倍数（6, 9, 12, 15, …）划掉（注意 6 已经被划掉了，但没关系）。
继续找下一个没被划掉的数，是 5，把 5 的倍数（10, 15, 20, …）划掉。
重复直到达到 √N（因为如果某个数大于 √N 且是合数，它一定有一个小于√N 的因子，已经被处理过了）。

最后，所有没有被划掉的数就是质数。

生活中的例子：想象全班 50 个同学站成一排，老师想找出所有身高超过 150cm 的同学。笨办法是拿尺子挨个量；筛法就像：先让所有身高是 2 的倍数的同学出列（比如 150cm、152cm 等），然后剩下的同学里，第一个身高是 3 的倍数的同学出列……最后剩下的就是那些身高不是任何整数倍数的同学（虽然这个比喻不完全准确，但可以帮助理解“筛”的过程）。

2. 算法步骤详解

我们用 Python 来实现。首先需要一个布尔列表 is_prime 来记录每个数是质数还是合数。长度为 n+1，因为下标从 0 到 n。

步骤1：初始化。假设所有数都是质数（True），但 0 和 1 不是质数，设为 False。

步骤2：从 2 开始循环，直到 p * p <= n。如果当前 p 是质数（is_prime[p] == True），就把 p 的所有倍数标记为合数。注意，从 p * p 开始标记，而不是从 p 的 2 倍开始，因为更小的倍数（如 2 * p）已经被更小的质数标记过了，这样可以避免重复标记，提高效率。

步骤3：循环结束后，从 is_prime 中找出所有值为 True 的下标，就是质数列表。

代码实现（带中文注释）：

def sieve_of_eratosthenes(n):
    # 初始化布尔列表，假设所有数都是质数
    is_prime = [True] * (n + 1)
    # 0 和 1 不是质数
    is_prime[0] = False
    is_prime[1] = False

    p = 2  # 从第一个质数开始
    while p * p <= n:  # 只需要检查到 sqrt(n)
        if is_prime[p]:  # 如果 p 是质数
            # 从 p*p 开始标记 p 的倍数
            for multiple in range(p * p, n + 1, p):  # 步长为 p
                is_prime[multiple] = False
        p += 1

    # 收集所有质数
    primes = [i for i in range(n + 1) if is_prime[i]]
    return primes

为什么从 p * p 开始？
例如：当 p = 5 时，5*2=10、5*3=15、5*4=20 这些数，其实早在处理 p=2 和 p=3 时就被标记过了。所以我们直接从 5*5=25 开始标记，避免重复劳动。这就好比打扫房间，你已经把小角落扫过了，就不用再扫一遍。

时间复杂度：埃氏筛法的时间复杂度是 O(n log log n)，对于 n=100 万，运算次数大约只有几百万次，在计算机上瞬间完成。

3. 新手容易犯的错误

错误1：忘记处理 0 和 1
很多同学只把 is_prime[0] 设为 False，但忘记 1 也不是质数，导致最后结果包含 1。

错误2：循环条件写成 p <= n
这样会一直标记到 n，效率很低（实际上 p 只需要到 √n 即可）。比如 n=100，p 只需要到 10，如果循环到 100，后面 11~100 的质数不会被标记，但 while p * p <= n 可以提前结束。

错误3：从 2 * p 而不是 p * p 开始标记
这样会导致重复标记，增加了运行时间。虽然结果正确，但会慢很多，尤其 n 很大时。

错误4：列表大小写错
is_prime = [True] * (n+1) 如果写成 [True] * n，那么下标 n 会越界。一定要加 1，因为我们要包含 0 到 n。

错误5：修改了 is_prime 列表的同时，在遍历时使用它
我们的代码中，在 for multiple 循环里修改 is_prime[multiple] 没问题，但注意不要在标记过程中依赖其他变量。这个代码是安全的。

4. 完整可运行示例

下面是一个完整版本，包含主程序、输入输出和中文注释，你可以直接复制运行：

def sieve_of_eratosthenes(n):
    """
    使用埃氏筛法找出 2 到 n 之间的所有质数
    :param n: 最大范围（正整数）
    :return: 质数列表
    """
    # 初始化布尔列表，长度为 n+1，下标对应数字
    is_prime = [True] * (n + 1)

    # 0 和 1 不是质数
    is_prime[0] = False
    is_prime[1] = False

    p = 2  # 从第一个质数开始
    while p * p <= n:  # 只需要处理到 sqrt(n)
        if is_prime[p]:  # 如果 p 是质数
            # 将 p 的所有倍数（从 p*p 开始）标记为合数
            for multiple in range(p * p, n + 1, p):
                is_prime[multiple] = False
        p += 1

    # 收集所有标记为 True 的数字
    primes = [i for i in range(n + 1) if is_prime[i]]
    return primes

# ----- 测试 -----
if __name__ == "__main__":
    n = 100  # 你想找出 1 到 100 之间的所有质数
    result = sieve_of_eratosthenes(n)
    print(f"1 到 {n} 之间的质数有:")
    print(result)
    print(f"共有 {len(result)} 个")

运行输出：

1 到 100 之间的质数有:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
共有 25 个

你也可以把 n 改成 1000、10000 测试，速度依然很快。

5. 相关知识点指引

判断单个质数：如果只需要判断一个数是不是质数，用试除法（检查 2 到 √n）更简单。但当需要大量质数时，筛法更高效。
线性筛法（欧拉筛）：埃氏筛法在标记时，一个合数可能被多个质因数重复标记（比如 12 会被 2 和 3 各标记一次）。线性筛法保证每个合数只被它的最小质因数标记一次，时间复杂度降为 O(n)，适合 n 极大的情况（比如 10^7 以上）。
质因数分解：结合筛法，我们可以快速获得一个数的所有质因数，常用于数论题目。
区间筛法：如果只需要一个很大区间（比如 [10^9, 10^9+10^5]）内的质数，可以用区间筛法，先筛出小质数，再标记大区间内的合数。

掌握素数筛法是 CSP-J 数论的基础，以后遇到“找质数”、“判断质数”、以及“质因数分解”相关题目时，它都能帮你快速解决。试试用筛法找出 1 到 1000 之间的质数个数吧！