埃拉托斯特尼筛法原理与优化实现

1. 埃拉托斯特尼筛法基础原理

1.1 算法起源与核心思想

公元前3世纪，古希腊数学家埃拉托斯特尼提出了一种寻找素数的巧妙方法。这个算法之所以被称为"筛法"，是因为它像筛子一样逐步过滤掉合数，最终留下所有的素数。算法的核心思想可以概括为：对于给定的上限n，从2开始依次标记每个素数的倍数，剩下的未被标记的数就是素数。

具体来说，算法执行过程如下：

1. 创建一个从2到n的连续整数列表
2. 从第一个数2开始，将其所有倍数标记为合数
3. 找到下一个未被标记的数，重复步骤2
4. 当处理完√n以内的所有数后，剩下的未被标记的数就是素数

这个算法之所以有效，是基于数论中的一个基本定理：任何合数都至少有一个不大于其平方根的素因数。因此，我们只需要筛选到√n就足够了。

1.2 基础实现示例

让我们用Python来实现最基本的埃氏筛：

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

这个实现有几个关键点需要注意：

1. 我们使用一个布尔数组is_prime来标记每个数是否为素数
2. 外层循环只需要遍历到√n（即int(n**0.5)+1）
3. 内层循环从current*current开始，因为更小的倍数已经被之前的素数筛过了
4. 最后我们收集所有标记为True的索引，即为素数列表

注意：在实现筛法时，常见的一个错误是内层循环从2*current开始。实际上，我们可以从current*current开始，因为更小的倍数已经被更小的素数筛过了。这个优化可以显著减少不必要的操作。

2. 经典筛法的现代优化

2.1 分段筛法优化

当我们需要处理非常大的n时（比如10^9以上），传统的埃氏筛会遇到内存问题。分段筛法（Segmented Sieve）通过将区间分成小块来处理，可以显著降低内存使用。

分段筛法的基本思路：

1. 先用普通筛法生成√n以内的所有素数
2. 将区间[2,n]分成多个大小为√n的小段
3. 对每一小段，用已得的素数来筛去该段中的合数

python复制def segmented_sieve(n, segment_size=None):
    if segment_size is None:
        segment_size = int(n**0.5)
    
    # 先用普通筛法得到基础素数
    base_primes = eratosthenes_sieve(int(n**0.5))
    
    primes = []
    low = 2
    high = min(low + segment_size - 1, n)
    
    while low <= n:
        sieve = [True] * (high - low + 1)
        
        for p in base_primes:
            # 计算第一个大于等于low的p的倍数
            first_multiple = max(p * p, ((low + p - 1) // p) * p)
            
            for multiple in range(