埃氏筛法：像筛沙子一样快速找到所有质数

质数是一个很神奇的数——它只有1和它本身两个因数，比如2、3、5、7、11……但是，如果让你找出100以内的所有质数，你会怎么做？一个数一个数地去检查，判断它有没有除了1和本身以外的因数，虽然可行，但太慢了，尤其是当数字大到1000、10000甚至100万的时候，电脑也会累趴下。

古希腊数学家埃拉托斯特尼想出了一个聪明的办法：像用筛子筛沙子一样，把合数（不是质数的数）一个个“筛掉”，剩下的就是质数。这个方法就叫埃氏筛法。它特别适合快速找出一定范围内（比如100以内、1000以内）的所有质数。

筛法到底怎么“筛”？

想象你面前有一张从2到100的数字表（或者更形象地说，你有一排写着数字的卡片，从2到100）。现在，我们开始筛选：

1. 第1步：找到最小的质数——2。它是质数，先把它保留下来，然后划掉所有2的倍数（4、6、8、10……一直到100）。为什么呢？因为这些数除了1和本身，至少还有因数2，所以它们不是质数。
2. 第2步：看下一个没有被划掉的数字——3。它没有被划掉，说明它是质数（因为比它小的质数2没能把它筛掉）。保留3，然后划掉所有3的倍数（6、9、12、15……）。注意，6已经被划掉了，没问题，我们继续划掉新的。
3. 第3步：下一个没被划掉的是5，保留，划掉5的倍数（10、15、20……）。
4. 第4步：下一个是7，保留，划掉7的倍数（14、21、28……）。
5. ……一直重复，直到我们划到哪个数为止呢？答案是**√100 = 10**。因为如果某个合数大于√100，它一定是由一个小于√100的质数相乘得到的，而这个质数的倍数已经被我们处理过了。所以，我们只需要处理到√n（n是范围的最大值）。

最后，所有没被划掉的数字就是质数！你会得到：[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]。

生活小例子：假设你们班有100个同学，学号从1到100。你想找出学号是质数的同学。你可以先让学号是2的同学站出来，然后让所有学号是2的倍数的同学（4、6、8……）都坐下（因为他们不是质数）。接着，看下一个还站着的同学（学号3），让他站出来，再让所有学号是3的倍数的同学坐下……一直做到学号10（√100）为止。最后还站着的同学，他们的学号就是质数。是不是很简单？

埃氏筛法的Python实现

下面我们用Python来模拟这个“筛”的过程。核心思想是：先假设所有数都是质数，然后用一个列表（或数组）来记录每个数的“质数状态”。我们从2开始，如果某个数是质数，就把它的倍数标记为“不是质数”。

def sieve_of_eratosthenes(n):
    """
    用埃氏筛法找出1到n之间的所有质数
    参数 n: 范围的上限（包含n）
    返回: 一个列表，包含所有小于等于n的质数
    """
    # 先假设所有数都是质数（True）
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False  # 0和1不是质数

    # 从2开始遍历到根号n（因为超过根号n的倍数已经在之前被筛过）
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:  # 如果i是质数，则筛掉它的倍数
            # 从i*i开始，因为i*2、i*3等已经被更小的质数筛过了
            for j in range(i * i, n + 1, i):
                is_prime[j] = False

    # 收集所有质数
    primes = [i for i in range(2, n + 1) if is_prime[i]]
    return primes

# 测试：输出100以内的所有质数
print("100以内的质数有：", sieve_of_eratosthenes(100))

代码一步步解释

1. is_prime = [True] * (n + 1)：我们创建一个长度为n+1的列表，下标从0到n。列表中的每个元素一开始都设为True，表示“暂时认为是质数”。比如，is_prime[2] = True表示2是质数，is_prime[3] = True表示3是质数……
2. is_prime[0] = is_prime[1] = False：0和1不是质数，所以直接设为False。
3. 外层循环for i in range(2, int(n ** 0.5) + 1)：i从2一直遍历到√n（四舍五入取整）。为什么只到√n？因为如果某个合数m有一个大于√n的因数a，那它必然还有一个小于√n的因数b（因为a×b=m），而这个b我们已经处理过了。
4. if is_prime[i]：如果i是质数（还没被筛掉），我们就筛掉它的倍数。
5. 内层循环for j in range(i * i, n + 1, i)：从i×i开始，每次加i，直到n。为什么从i×i开始？想象一下，当我们处理到质数i=5时，5的倍数有10、15、20、25……其中，5×2=10已经被质数2筛过了，5×3=15已经被质数3筛过了，5×4=20已经被质数2筛过了（因为4是2的倍数）。所以，最小的还没有被筛掉的5的倍数是5×5=25。因此从i×i开始可以避免重复工作，让程序更快。
6. is_prime[j] = False：把j标记为合数（不是质数）。
7. 列表推导式primes = [i for i in range(2, n + 1) if is_prime[i]]：遍历2到n，把is_prime中还是True的下标i收集起来，这些就是质数。

运行结果会打印出：

100以内的质数有： [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

新手容易犯的几个错误

虽然埃氏筛法的代码看起来不长，但写的时候有几个地方特别容易出错：

1. 忘记处理0和1：很多人直接is_prime = [True] * (n+1)就开干了，忘了把0和1单独设为False。结果质数列表里可能会多出0和1，让人一头雾水。
2. 内层循环从i×2开始：比如写成for j in range(i*2, n+1, i)。这样虽然没错，但会做很多重复工作，降低速度。更规范的写法是从i*i开始，因为比它小的倍数已经被更早的质数筛过了。
3. 外层循环范围写错：一些人写成for i in range(2, n+1)，会导致循环次数太多，虽然结果可能也对，但效率低。记住，只需要到int(n**0.5)就可以了。
4. 忘记加1：比如range(2, int(n**0.5))会漏掉边界。因为如果n是完全平方数（比如100），√100=10，我们需要处理到10，所以循环条件要写成int(n**0.5) + 1。
5. 列表下标越界：is_prime的长度是n+1，最大下标是n。内层循环range(i*i, n+1, i)能保证j最大为n，但如果n比较小（比如n=3），i*i可能大于n，此时内层循环不会执行，这没问题。

完整可运行的示例：让用户自己输入范围

下面的代码可以让用户输入一个数字n，然后输出从2到n的所有质数，并告诉用户一共有多少个。

def sieve_of_eratosthenes(n):
    """埃氏筛法，返回n以内所有质数列表"""
    # 先假设所有数都是质数（True）
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False  # 0和1不是质数

    # 从2开始遍历到根号n
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:  # 如果i是质数，则筛掉它的倍数
            for j in range(i * i, n + 1, i):
                is_prime[j] = False

    # 收集所有质数
    primes = [i for i in range(2, n + 1) if is_prime[i]]
    return primes

# 让用户输入一个整数
num = int(input("请输入一个正整数（比如100），程序将输出该数以内的所有质数："))

# 调用函数并输出
result = sieve_of_eratosthenes(num)
print(f"{num}以内的质数有：{result}")
print(f"一共有{len(result)}个质数。")

运行一下：

请输入一个正整数（比如100），程序将输出该数以内的所有质数：50
50以内的质数有：[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
一共有15个质数。

埃氏筛法有多快？

埃氏筛法的时间复杂度大约是 O(n log log n)。这是什么意思呢？n是范围大小。当n=100时，几毫秒就完成；当n=100万时，也只需要不到0.1秒；当n=1000万时，大约需要0.5秒。这可比一个一个数去试除法快太多了！

不过，如果你需要处理非常大的数据（比如1亿以上），埃氏筛法可能会占用较多内存（因为要存储一个长度为n的布尔列表）。这时候还有更高效的算法，比如欧拉筛（线性筛），可以让每个合数只被筛一次，速度更快。

学完这个，还可以学什么？

1. 试除法判断单个质数：如果你只想判断一个数是不是质数（而不是找出一堆），可以用试除法——从2试到√n，看有没有因数。代码更简单，但判断多个数时效率低。
2. 质因数分解：埃氏筛法可以帮我们快速得到质数表，然后用来分解一个合数的质因数。比如分解180 = 2×2×3×3×5。
3. 欧拉筛（线性筛）：比埃氏筛法更快更节省内存，每个合数只被它的最小质因子筛一次。如果你对算法优化感兴趣，可以去研究一下。
4. 质数的应用：密码学中的RSA加密算法依赖大质数，还有哈希表设计、随机数生成等。质数真的无处不在！

埃氏筛法是一个简单又强大的算法，掌握它之后，你就能轻松找出任何范围内的所有质数了。快去动手试试吧！