埃拉托斯特尼筛法：质数筛选的高效算法解析

1. 埃拉托斯特尼筛法：穿越千年的质数筛选智慧

在计算机科学和数学领域，寻找质数一直是个经典问题。埃拉托斯特尼筛法（简称埃氏筛）作为最古老的质数筛选算法之一，至今仍被广泛应用。这个由古希腊数学家埃拉托斯特尼在公元前3世纪提出的算法，以其简洁高效的特点，成为了算法入门学习的绝佳案例。

我第一次接触这个算法是在大学的数据结构课上，当时就被它那优雅的思路所吸引。相比暴力判断每个数是否为质数的方法，埃氏筛通过"筛除"合数的方式，将时间复杂度从O(n√n)降低到了O(n log log n)，这在处理大规模数据时优势尤为明显。

2. 算法原理深度解析

2.1 基本思想：筛除的艺术

埃氏筛的核心思想可以用一个生活化的比喻来理解：想象你有一张写满数字的纸，从2开始，你圈出第一个未被标记的数（它一定是质数），然后划掉它的所有倍数。重复这个过程，最终所有被圈出的数就是质数。

具体来说，算法步骤如下：

1. 创建一个从2到n的连续整数列表
2. 初始化p为2（第一个质数）
3. 从p开始，依次标记p的倍数（2p, 3p, 4p,...）为合数
4. 找到列表中大于p的第一个未被标记的数，将其作为新的p值
5. 重复步骤3-4，直到p² > n
6. 所有未被标记的数即为质数

2.2 数学基础：为什么这样有效？

这个算法之所以有效，基于数论中的一个基本定理：任何合数都可以表示为质数的乘积。因此，当我们从小到大依次筛除每个质数的倍数时，就能确保所有合数都被标记。

举个例子，考虑n=30的情况：

• 第一轮：p=2，筛除4,6,8,10,12,14,16,18,20,22,24,26,28,30
• 第二轮：p=3，筛除9,15,21,27
• 第三轮：p=5，筛除25
  此时p=7，7²=49>30，算法终止

剩下的未被筛除的数2,3,5,7,11,13,17,19,23,29就是30以内的所有质数。

3. 算法实现与优化

3.1 基础实现（Python示例）

python复制def eratosthenes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = is_prime[1] = False
    
    for p in range(2, int(n**0