素数筛法：埃氏筛与欧拉筛的算法原理与优化实践

1. 筛法基础与需求解析

素数筛选算法是数论和计算数学中的经典问题，也是编程竞赛和算法面试的高频考点。在实际开发中，我们经常需要快速获取一定范围内的所有素数——比如密码学中的密钥生成、哈希算法设计，或者解决某些数学问题时。传统遍历判断法的时间复杂度高达O(n√n)，当n达到1e6以上时就显得力不从心。

埃拉托斯特尼筛法（埃氏筛）和欧拉筛（线性筛）是两种主流的优化算法。我在ACM竞赛和实际工程项目中多次使用这两种算法，发现很多教程只给出代码而缺乏关键细节的剖析。本文将结合我的实战经验，从算法原理、实现细节到性能对比，带你彻底掌握这两种筛法的精髓。

2. 埃氏筛深度解析

2.1 算法原理与基础实现

埃氏筛的核心思想非常直观：从2开始，将每个素数的倍数都标记为合数。就像用筛子过滤数字，留下的就是素数。下面是一个典型的实现：

python复制def eratosthenes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    return [i for i, prime in enumerate(is_prime) if prime]

关键点：内层循环从ii开始而非2i，因为更小的倍数已经被之前的素数筛过了。这个优化能减少约30%的操作量。

2.2 性能优化实践

虽然埃氏筛的时间复杂度是O(n log log n)，但通过以下优化可以显著提升实际运行速度：

1. 按奇偶分治：除了2，所有偶数都不是素数。可以特殊处理2，然后只考虑奇数：

python复制def eratosthenes_optimized(n):
    if n < 2: return []
    is_prime = [True] * ((n + 1) // 2)  # 只存储奇数
    is_prime[0] = False  # 1不是素数
    for i in range(1, int(n ** 0.5) // 2 + 1):
        if is_prime[i]:
            p = 2 * i + 1
            start = p * p // 2  # 计算在压缩数组中的位置
            step = p
            for j in range(start, len(is_prime), step):
                is_prime[j] = False
    primes = [2]
    primes.extend(2*i+1 for i, prime in enumerate(is_prime) if prime)
    return primes

2. 内存访问优化：使用位运算代替布尔数组，内存占用减少为1/8：

python复制import sys
def eratosthenes_bits(n):
    if n < 2: return []
    size = (n + 1) // 2
    is_prime = bytearray([0xFF]) * ((size + 7) // 8)
    def get_bit(i):
        return (is_prime[i//8] >> (i%8)) & 1
    def clear_bit(i):
        is_prime[i//8] &= ~(1 << (i%8))
    clear_bit(0)  # 1不是素数
    for i in range(1, int(n**0.5)//2 + 1):
        if get_bit(i):
            p = 2*i + 1
            for j in range(p*p//2, size, p):
                clear_bit(j)
    primes = [2]
    primes.extend(2*i+1 for i in range(size) if get_bit(i))
    return primes

2.3 埃氏筛的局限性

尽管埃氏筛已经比朴素算法快很多，但它存在两个本质缺陷：

1. 同一个合数会被多个素数重复标记（如15会被3和5标记）
2. 内存访问模式不连续，在大数据量时缓存命中率低

在我的测试中，当n=1e8时，优化后的埃氏筛在i7-11800H上需要约1.2秒，而接下来的欧拉筛仅需0.6秒。

3. 欧拉筛精讲

3.1 线性筛原理揭秘

欧拉筛的精妙之处在于确保每个合数只被其最小质因数筛除一次。算法维护一个素数列表，并用当前数与已知素数的乘积来标记合数：

python复制def euler_sieve(n):
    is_prime = [True] * (n + 1)
    primes = []
    for i in range(2, n + 1):
        if is_prime[i]:
            primes.append(i)
        for p in primes:
            if i * p > n:
                break
            is_prime[i * p] = False
            if i % p == 0:  # 关键点
                break
    return primes

核心技巧：当i能被p整除时立即break，这保证了每个合数只被标记一次。例如i=4时，在标记4×2=8后立即停止，避免了后续标记4×3=12（因为12会被6×2标记）。

3.2 正确性证明

为什么这个算法能保证线性复杂度？关键在于：

1. 每个合数n都会被其最小质因数p筛除（当i=n/p时）
2. 由于遇到i%p==0就break，确保每个合数只被标记一次

数学证明：

• 设n的最小质因数为p₁，令i=n/p₁
• 在遍历i时，必定会遇到p₁（因为p₁≤i的所有质因数）
• 在标记i×p₁后立即break，不会处理更大的质因数p₂

3.3 内存与性能优化

欧拉筛的瓶颈在于素数列表的内存访问。当n=1e8时，素数列表约占60MB内存。我们可以采用以下优化：

1. 预分配内存：根据素数定理预估素数数量π(n)≈n/ln(n)

python复制import math
def euler_optimized(n):
    is_prime = bytearray([1]) * (n + 1)
    primes = bytearray()  # 预分配空间
    prime_count_estimate = int(1.2 * n / math.log(n))  # 20% buffer
    primes = [0] * prime_count_estimate
    count = 0
    for i in range(2, n + 1):
        if is_prime[i]:
            primes[count] = i
            count += 1
        for j in range(count):
            if i * primes[j] > n:
                break
            is_prime[i * primes[j]] = 0
            if i % primes[j] == 0:
                break
    return primes[:count]

2. 分段筛法：处理超大范围时（如n>1e9），将区间分成小块依次处理，减少内存压力

4. 实战对比与性能测试

4.1 时间复杂度实测

在我的测试环境（Python 3.9, i7-11800H）下，不同算法的表现：

当n=1e8时：

• 欧拉筛：约3600ms
• 位运算埃氏筛：约4200ms

4.2 选择建议

根据场景选择合适算法：

1. 内存敏感：使用位运算版埃氏筛
2. 速度优先：欧拉筛是最佳选择
3. 超大范围（n>1e9）：考虑分段筛法组合欧拉筛

5. 常见问题与调试技巧

5.1 典型错误排查

1. 数组越界：

   • 确保数组大小为n+1（包含0到n）
   • 在埃氏筛中，内层循环的起始点i*i可能溢出，应添加检查

2. 漏筛问题：

   • 欧拉筛中忘记if i%p==0: break会导致重复标记
   • 埃氏筛的内层循环步长错误（应用i而非1）

3. 性能异常：

   • Python中使用列表而非numpy数组时，大数据量会变慢
   • 可以尝试用numpy.zeros(..., dtype=bool)替代普通列表

5.2 算法扩展应用

1. 筛法求欧拉函数：

python复制def euler_phi(n):
    is_prime = [True] * (n + 1)
    phi = [i for i in range(n + 1)]
    for i in range(2, n + 1):
        if is_prime[i]:
            phi[i] = i - 1
            for j in range(2 * i, n + 1, i):
                is_prime[j] = False
                phi[j] = phi[j] // i * (i - 1)
    return phi

2. 筛法求最小质因数：

python复制def min_prime_factors(n):
    spf = [0] * (n + 1)
    spf[0], spf[1] = 0, 1
    for i in range(2, n + 1):
        if spf[i] == 0:
            spf[i] = i
            for j in range(i * i, n + 1, i):
                if spf[j] == 0:
                    spf[j] = i
    return spf

在实际项目中，我经常使用欧拉筛的变种来预处理质因数分解。例如预先计算每个数的最小质因数后，可以在O(log n)时间内完成任意数的质因数分解。