埃拉托斯特尼筛法：用筛子快速找出所有质数

这是什么？用来干什么？

想象你有一大堆混在一起的沙子和石子，想只留下石子，怎么办？用筛子！数学里也有一种“筛子”，能把合数（像沙子）筛掉，剩下的就是质数（像石子）。这个筛子叫埃拉托斯特尼筛法，简称埃氏筛，是古希腊数学家埃拉托斯特尼在两千多年前发明的。它专门用来快速找出某个范围（比如1到100、1到10000）以内的所有质数，是编程竞赛和数学研究里最经典、最基础的算法之一。

生活中的例子：筛沙子 vs 筛质数

还记得去海边玩时用筛子筛沙子的情景吗？筛子的网眼很小，沙子能漏下去，但小石子、贝壳碎片会留在筛网上。埃氏筛正好相反——它把合数（像沙子）标记并“筛掉”，而让质数（像石子）保留下来。

换个更贴近你生活的例子：假设你班上有30个同学，学号从1到30。你想找出学号是质数的同学（比如2号、3号、5号、7号……）。最笨的办法是挨个检查每个学号能不能被比它小的数字整除，但太慢了。埃氏筛的方法是这样的：

先假设所有同学（除了1号）都是质数，在名单上打勾。
从2号开始：2号是质数，那么所有学号是2的倍数的同学（4、6、8……）都不是质数，把他们名字划掉。
下一个还没被划掉的是3号：3号是质数，把所有3的倍数（6、9、12……）划掉。注意，6已经被划过了，没关系，再划一次也不影响。
再下一个是5号：5号是质数，从5×5=25开始划，因为5×2=10、5×3=15、5×4=20已经被更小的质数（2和3）划过了，不用再重复。
继续，7号是质数，但7×7=49已经超过30，所以不需要再划任何数。
剩下的所有没被划掉的同学，就是质数啦！

你看，用这个方法，你只需要划几次（每次划掉一些倍数），就轻轻松松筛出了所有质数，根本不用一个个去试除法。

核心思想与关键要点

1. 怎么筛？——从2开始，标记倍数

核心步骤只有三步：

准备：把2到n的所有数字都标记为“可能是质数”（比如用true表示）。
筛选：从2开始，如果当前数字i是质数（还没被标记为合数），就把i的所有倍数（除了i本身）标记为合数。注意，从i×i开始标记，不是从i×2开始。
继续：重复上一步，直到i大于√n。

再重复一遍：从i×i开始，而不是i×2。为什么？因为i×2、i×3……i×(i-1)这些倍数，已经被比i小的质数标记过了。比如i=5时，5×2=10，在i=2时已经被标记；5×3=15，在i=3时已被标记；5×4=20，也被2标记过。所以从i×i=25开始标记，可以避免很多重复工作，让筛子更快。

很多同学会问：“为什么到了√n就可以停了？后面的数字不用管吗？”我们来推理一下：如果一个数k是合数，那么它一定可以拆成两个大于1的因数相乘，比如k = a × b，其中a ≤ b。那么a一定小于等于√k，b一定大于等于√k。换句话说，每个合数都有一个不超过它平方根的因数。所以，只要我们用所有不超过√n的质数，把它们所有的倍数都标记一遍，那些大于√n的合数（比如n=30时的21，它等于3×7，3已经在≤√30的质数里，所以21已经被标记了）都会被这些较小的质数标记掉。因此，我们只需要处理到√n，就能保证所有合数都被筛掉。

举个例子：n=100，√100=10。从2到10的质数有2、3、5、7。它们把所有100以内的合数都标记干净了——比如91=7×13，13>10，但因数7已经被处理，所以91被标记；97是质数，没被标记。你看，后面的11、13、17……本身是质数，不需要标记任何倍数（它们的平方都超过100了），所以不用再处理。

3. 时间复杂度：O(n log log n)

埃氏筛快在哪里？我们只需要对每个质数p，标记大约n/p个倍数。所有质数p的n/p加起来大约等于n × (1/2 + 1/3 + 1/5 + 1/7 + …)。这个级数的和增长非常慢，大约是log log n。所以总操作次数大约为n × log log n。例如n=10⁷时，log log 10⁷ ≈ log(16.1) ≈ 2.78，总操作约2.78×10⁷次，现代计算机一秒内就能算完。而如果用试除法（每个数都检查因数），复杂度是O(n√n)，n=10⁷时就要10¹⁰次，慢上千倍。

4. 空间复杂度：O(n)

我们需要一个长度为n+1的布尔数组来标记每个数是否为质数，所以需要O(n)的内存。n=10⁷时，如果用C++的vector<bool>（每个元素占1位），只需要约1.25MB；如果用Python列表（每个元素是Python对象，约28字节），则需要280MB，会爆内存。所以实际编程时要注意语言和数据类型的选择，Python可以用bytearray或array('b')来节省空间。

新手容易犯的错误

忘记标记0和1：0和1不是质数，必须手动设为false。否则程序会把它们当作质数输出，导致错误。
循环终点写错：外层循环写成for i in range(2, n+1)而不是range(2, sqrt_n+1)，这会多做很多无用功（因为大于√n的i如果是质数，它的倍数已经超出范围，不用再标记），但结果正确，只是慢。更严重的是写成for i in range(2, n)漏掉n本身，导致n如果本身是质数则不会输出。
内层循环从i*2开始：没有从i*i开始，导致重复标记很多倍数，虽然结果正确但效率降低。
数组越界：在内层循环中，j = i*i可能超过int范围（比如i=46349时，i*i>2³¹-1），在C++中会导致溢出变成负数或错误值。可以用long long或将条件写成j <= n / i来避免。
**在Python中使用range(i*i, n+1, i)时，如果i很大，i*i可能会超出Python的整数范围？Python整数无限大，所以不会溢出，但非常慢。通常n在10⁷以内没问题。
误用vector<bool>的特殊性：C++中vector<bool>不是标准容器，不能取引用，也不能用auto&遍历，可能导致编译错误。如果不需要极致省内存，可以用vector<char>。

完整可运行的代码示例

下面分别给出C++和Python的完整代码，附带详细的中文注释。你可以直接复制到本地运行，试试输入不同的n值。

C++ 版（使用 `vector<bool>` 节省空间）

#include <iostream>
#include <vector>
#include <cmath>   // 用于 sqrt 函数

using namespace std;

// 埃拉托斯特尼筛法，返回 n 以内所有质数的列表
vector<int> sieveOfEratosthenes(int n) {
    // 特殊情况：n<2 时没有质数
    if (n < 2) return {};

    // 创建布尔数组，下标从 0 到 n，默认全部为 true
    // vector<bool> 是特化版本，每个元素只占 1 位（bit），非常省内存
    vector<bool> isPrime(n + 1, true);
    // 0 和 1 不是质数，手动标记
    isPrime[0] = isPrime[1] = false;

    // 只需要检查到 sqrt(n) 即可
    int sqrt_n = static_cast<int>(sqrt(n));
    for (int i = 2; i <= sqrt_n; ++i) {
        // 如果 i 还是质数（没被标记为合数）
        if (isPrime[i]) {
            // 从 i*i 开始标记，步长为 i
            // 注意：j 从 i*i 开始，因为更小的倍数已被更小的质数标记过
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;   // 标记为合数
            }
        }
    }

    // 收集所有 isPrime 为 true 的下标，即为质数
    vector<int> primes;
    for (int i = 2; i <= n; ++i) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
    }
    return primes;
}

int main() {
    int n;   // 用户输入的整数上限
    cout << "请输入一个整数 n（n≥2）：";
    cin >> n;

    vector<int> primes = sieveOfEratosthenes(n);

    cout << n << " 以内的质数共有 " << primes.size() << " 个：" << endl;
    // 每行输出 10 个，方便查看
    for (size_t i = 0; i < primes.size(); ++i) {
        cout << primes[i] << " ";
        if ((i + 1) % 10 == 0) cout << endl;
    }
    cout << endl;

    return 0;
}

运行示例：

请输入一个整数 n（n≥2）：100
100 以内的质数共有 25 个：
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

Python 版（使用列表 + 内存优化建议）

import math

def sieve_of_eratosthenes(n: int):
    """
    使用埃拉托斯特尼筛法找出 n 以内的所有质数。
    返回一个列表，包含所有质数。
    """
    if n < 2:
        return []

    # 创建布尔列表，下标从 0 到 n，全部初始化为 True
    # 注意：Python 列表每个元素是对象，占用内存较大
    # 对于大 n（例如 10^7 以上），建议改为 bytearray 节省内存
    is_prime = [True] * (n + 1)
    # 0 和 1 不是质数
    is_prime[0] = is_prime[1] = False

    # 只需要检查到 sqrt(n)
    # 使用 math.isqrt 可以得到精确的整数平方根，避免浮点误差
    sqrt_n = math.isqrt(n)
    for i in range(2, sqrt_n + 1):
        if is_prime[i]:
            # 从 i*i 开始标记，步长为 i
            # 注意：range(start, stop, step) 中 stop 是 n+1 以包含 n
            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

def main():
    try:
        n = int(input("请输入一个整数 n（n≥2）："))
    except ValueError:
        print("输入无效，请输入一个整数。")
        return

    primes = sieve_of_eratosthenes(n)
    print(f"{n} 以内的质数共有 {len(primes)} 个：")
    # 每行输出 10 个
    for i in range(0, len(primes), 10):
        print(" ".join(map(str, primes[i:i+10])))

if __name__ == "__main__":
    main()

运行示例：

请输入一个整数 n（n≥2）：30
30 以内的质数共有 10 个：
2 3 5 7 11 13 17 19 23 29

手动模拟小例子：n=30

为了让你更直观地理解筛的过程，我们手动模拟一遍 n=30 时数组的变化（用 1 表示质数，0 表示合数）：

初始：下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
标记：0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

第1步：i=2，是质数，标记 4,6,8,10,12,14,16,18,20,22,24,26,28,30 为 0
结果：0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

第2步：i=3，是质数（isPrime[3]=1），从 9 开始标记 9,12,15,18,21,24,27,30 为 0（注意 12,18,24,30 已经是0）
结果：0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0

第3步：i=4，不是质数（isPrime[4]=0），跳过

第4步：i=5，是质数（isPrime[5]=1），从 25 开始标记 25,30 为 0
结果：0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0

第5步：i=6，不是质数；i=7（≤√30≈5.5，实际上 i=7 时 i*i=49>30，所以循环到 sqrt_n=5 就结束了。但为了演示，我们手动检查到 7：isPrime[7]=1，但 49>30，所以内循环不执行。后面的 i 都不用标记了。）

最终剩下的质数下标：2,3,5,7,11,13,17,19,23,29 —— 恰好10个。

埃拉托斯特尼筛法（埃氏筛）