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

1. 埃拉托斯特尼算法入门：筛出质数的古老智慧

第一次听说埃拉托斯特尼算法时，我正被一道需要快速找出100万以内所有质数的编程题难住。当时我天真地用了最直接的暴力解法——对每个数都检查是否能被小于它的数整除，结果程序运行了整整十分钟还没出结果。直到一位学长告诉我："试试埃氏筛吧，同样的任务它只需要几毫秒。"这个诞生于公元前3世纪的算法，至今仍是寻找质数最高效的方法之一。

埃拉托斯特尼（Eratosthenes）是古希腊著名的数学家、地理学家，他发明的这个筛法原理简单却极其巧妙。算法的核心思想就像用筛子过滤杂质——先把所有数放入"筛子"中，然后通过特定的筛选规则，逐步筛掉合数，最后剩下的就是质数。这种思想在现代计算机科学中依然闪耀着智慧的光芒，特别是在需要高效处理数论问题的场景下。

2. 算法原理深度解析

2.1 基本筛法流程

埃氏筛的工作流程可以用一个简单的例子来说明。假设我们要找出30以内的所有质数：

1. 初始化一个从2到30的整数列表，全部标记为质数（True）
2. 从第一个数2开始（已知是质数），将所有2的倍数（4,6,8...）标记为非质数（False）
3. 移动到下一个未被标记的数3，将所有3的倍数（6,9,12...）标记为非质数
4. 重复这个过程，直到处理完√30≈5.47（即只需要处理到5）
5. 最后，所有仍被标记为True的数就是质数

这个过程中有几个关键点需要注意：

• 我们只需要检查到√n的原因：任何大于√n的合数必然有一个小于等于√n的质因数
• 每次找到一个新的质数p时，我们可以从p²开始标记它的倍数，因为更小的倍数已经被之前的质数处理过了

2.2 算法的时间复杂度分析

埃氏筛的时间复杂度是O(n log log n)，这比暴力检查每个数的O(n√n)要高效得多。这个复杂度可能看起来有些奇怪，它来自于数论中的一个结论——质数的倒数和的渐进行为。

为了理解为什么不是O(n)，我们可以这样思考：对于每个质数p，我们需要标记n/p个它的倍数。根据素数定理，小于n的质数大约有n/ln n个，所以总操作量大约是n×(1/2 + 1/3 + 1/5 + ... + 1/p)，其中p≤√n。这个和就是log log n的量级。

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.5) + 1):
        if is_prime[p]:
            for multiple in range(p*p, n+1, p):
                is_prime[multiple] = False
                
    primes = [i for i, prime in enumerate(is_prime) if prime]
    r