质数筛法全解析：从基础到优化，高效求解质数的核心方法

质数（又称素数），是指大于1的自然数中，除了1和它本身以外不再有其他正因数的数。质数作为数论的核心概念，广泛应用于密码学、算法设计、数论研究等多个领域。在实际应用中，我们常常需要快速找出一定范围内的所有质数，这就需要借助高效的“质数筛法”——一种通过特定规则排除非质数，从而筛选出质数的算法。本文将从基础筛法入手，逐步深入优化思路，详解几种经典质数筛法的原理、实现、优缺点及适用场景，帮助读者彻底掌握质数筛选的核心逻辑。

一、前置知识：质数的核心判定要点

在学习筛法之前，我们先明确几个关键前提，避免后续理解偏差：

质数的范围：仅针对大于1的自然数，1既不是质数也不是合数；
质数的判定本质：若一个数n（n>1）不能被任何大于1且小于√n的数整除，则n是质数（因为若n存在大于√n的因数，其对应的另一个因数必然小于√n，只需验证到√n即可减少计算量）；
筛法的核心思想：“排除法”——先假设所有数都是质数，再通过规则逐步排除非质数（合数），剩余的即为目标范围内的质数。

二、基础筛法：枚举筛法（试除法）

2.1 原理

枚举筛法（也叫试除法）是最直观、最基础的质数筛选方法，核心逻辑的是：对于每个需要判断的数n，逐一验证它是否能被2到√n之间的任何整数整除。若能被整除，则n是合数；若不能，则n是质数。

这种方法本质上是“逐个判定”，没有利用数与数之间的关联，属于暴力筛选，但胜在逻辑简单、易于实现，适合初学者入门，也适合小范围（如n≤10⁵）的质数筛选。

2.2 实现步骤（以筛选1~N的所有质数为例）

初始化一个空列表，用于存储筛选出的质数；
遍历从2到N的每一个整数n；
对于每个n，遍历从2到√n的每一个整数i；
若n能被i整除（即n%i == 0），说明n是合数，跳出循环，不再验证后续i；
若遍历完2到√n的所有i，n都不能被整除，说明n是质数，将其加入质数列表；
遍历结束后，质数列表中即为1~N的所有质数。

2.3 代码实现（Python）

def enum_sieve(n):
    primes = []
    for num in range(2, n+1):
        is_prime = True
        # 只需验证到sqrt(num)，减少计算量
        for i in range(2, int(num**0.5) + 1):
            if num % i == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(num)
    return primes

# 测试：筛选1~100的质数
print(enum_sieve(100))

2.4 优缺点

优点：逻辑简单、代码简洁，无需额外空间存储中间状态（除了质数列表），对于小范围数据（n≤10⁵）效率可接受。

缺点：效率极低，存在大量重复计算。例如，判断101是否为质数时，需要验证2到10之间的所有数；判断103时，又要重复验证2到10之间的数，没有利用之前的判定结果。当n较大（如n≥10⁶）时，时间复杂度会急剧上升，无法满足需求。

时间复杂度：O(n√n)，其中n为筛选范围；空间复杂度：O(k)，k为1~n之间的质数个数（最坏情况下k≈n/lnn）。

三、经典优化筛法：埃拉托斯特尼筛法（Eratosthenes Sieve）

埃拉托斯特尼筛法（简称埃氏筛）是古希腊数学家埃拉托斯特尼提出的一种高效筛法，核心改进是“利用质数的倍数排除合数”，避免了枚举筛法的重复计算，是日常应用中最常用的基础优化筛法。

3.1 原理

埃氏筛的核心逻辑：质数的所有倍数都是合数（除了质数本身）。因此，我们可以先假设所有数都是质数（用一个布尔数组标记，初始值为True，索引代表数字，值为True表示是质数），然后从第一个质数（2）开始，将其所有倍数（4、6、8、…）标记为合数（False）；接着处理下一个未被标记为合数的数（3），将其所有倍数（6、9、12、…）标记为合数；以此类推，直到处理完√N的所有数，剩余未被标记的数即为质数。

关键优化点：无需处理大于√N的数——因为大于√N的合数，其最小因数必然小于√N，早已被对应的质数标记过（例如，100的最小因数是2，小于√100=10，在处理2时就已被标记为合数），因此无需额外处理。

质数判定与质数筛