埃氏筛法：快速找出所有小质数

当你需要找出从 2 到 100（或更大范围）的所有质数时，埃氏筛法就像一个魔法筛子——它先把所有数都当作“可能质数”，然后一步步筛掉那些不是质数的合数（比如 4、6、8……），最后留在筛子里的就是真正的质数。这种方法简单又好用，是编程中解决“找质数”问题的经典方法。

什么是质数？用积木和排队来理解

质数就像只有两种积木的乐高块：1 和它自己。比如：

2 只能拆成 1×2
3 只能拆成 1×3
5 只能拆成 1×5 它们都是“孤独”的数，没法用其他整数相乘拼出来。

合数则像可以拆成更多积木的乐高块，比如：

4 = 2×2（两个 2）
6 = 2×3（一个 2 和一个 3）
15 = 3×5

生活中的例子：假设全班同学按人数分组做游戏。如果班级人数是质数（比如 23 人），那么不可能分成人数相等的几个小组（除了 1 组或 23 组）。如果人数是合数（比如 24 人），就可以分成 2 组每组 12 人，或 3 组每组 8 人等等。

注意：1 不是质数也不是合数，它只有自己一个因数。

埃氏筛法的思路：像筛沙子一样筛掉合数

想象你有一排从 2 到 100 的卡片，起初它们都是“嫌疑人”，你怀疑它们可能是质数。接下来，你从最小的质数 2 开始，把 2 的倍数（4, 6, 8, 10……）全部划掉，因为这些数除了 1 和本身，至少还有因数 2，所以它们不能是质数。

然后看下一个还没被划掉的数——3。3 是质数（因为 2 的倍数中已经没有 3 了），于是把 3 的倍数（6, 9, 12, 15……）划掉。

继续看 4，它已经被划掉了，跳过。下一个是 5……这样一直做到最后一个数，最后没被划掉的卡片就是所有质数。

关键优化：划掉某个质数的倍数时，从该质数的平方开始，而不是从它的两倍开始。为什么？因为比如划掉 5 的倍数时，5×2=10 已经在 2 的倍数中被划掉了，5×3=15 在 3 的倍数中被划掉了，5×4=20 在 2 的倍数中也已经被划掉。所以第一次没被划掉的 5 的倍数是 5×5=25。这样就能避免重复工作，让程序跑得更快。

用 C++ 代码实现埃氏筛法

下面这段代码会找出 2 到 n 之间的所有质数，并打印出来。我们用布尔数组 isPrime 来标记每个数是不是质数，有点像在卡片上做记号。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 100;                         // 要找 1~100 之间的质数
    vector<bool> isPrime(n + 1, true);   // 先假设所有数都是质数（true 表示质数）
    isPrime[0] = false;                  // 0 不是质数
    isPrime[1] = false;                  // 1 也不是质数

    // 从 2 开始，一直检查到 根号n（因为更大的数的平方会超过 n）
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {                // 如果 i 还是质数（没被筛掉）
            // 从 i*i 开始，每次加 i，把 i 的倍数全部标记为 false（不是质数）
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;      // 筛掉 j
            }
        }
    }

    // 输出所有质数
    cout << "2 到 " << n << " 之间的质数有：";
    for (int num = 2; num <= n; num++) {
        if (isPrime[num]) {
            cout << num << " ";
        }
    }
    cout << endl;
    return 0;
}

运行结果：

2 到 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

代码逐行解释

int n = 100; —— 设置要找的最大范围。你可以改成 1000 或 10000，只要电脑内存够。
vector<bool> isPrime(n + 1, true); —— 创建一个布尔数组，长度为 n+1（因为数组下标从 0 到 n），初始值全部为 true，意思是“暂时认为是质数”。
isPrime[0] = false; isPrime[1] = false; —— 0 和 1 不是质数，直接排除。
外层循环 for (int i = 2; i * i <= n; i++) —— 只循环到 i * i <= n，因为如果 i 大于 √n，i 的倍数（从 i*i 开始）已经超过 n 了，没必要再筛。
if (isPrime[i]) —— 如果 i 当前还是质数（没被筛掉），才进入内层循环。如果 i 已经被筛掉（比如 4），那它不会产生任何新结果，跳过。
内层循环 for (int j = i * i; j <= n; j += i) —— 从 i 的平方开始，每次加 i，把 j 标记为 false。为什么从 ii 开始？因为小于 ii 的 i 的倍数（比如 i×2, i×3, ..., i×(i-1)）已经被更小的质数筛过了。

新手最容易犯的错误

1. 数组下标越界或忘记包含 n

很多人会写成 vector<bool> isPrime(n, true);，这样下标只能到 n-1，却要访问 isPrime[n]，导致数组越界。正确的做法是长度设为 n+1，下标 0~n 都可用。

2. 外层循环条件写成 `i <= n`

如果循环到 n，内层循环从 i*i 开始可能超过 n 就不执行了，但会浪费很多时间。用 i * i <= n 更高效。

3. 忘记初始化 isPrime[0] 和 isPrime[1]

如果不手动设置 0 和 1 为 false，程序会错误地把它们当成质数输出。一定要单独处理 0 和 1。

4. 内层循环从 i2 开始（而不是 ii）

这样会重复筛掉很多合数，导致速度变慢，但不会出错。不过为了学习正确的优化，建议从 i*i 开始。

5. 在输出时误把下标当值

比如习惯用 i 当循环变量，输出时写 cout << i 是没问题的，但要注意 isPrime[i] 和 i 的关系。代码中用 num 作为输出变量名比较清晰。

完整可运行的例子（可自定义 n）

下面这个版本允许用户输入 n，然后输出所有质数，适合自己测试不同范围。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;                               // 存储用户输入的最大范围
    cout << "请输入一个正整数 n：";
    cin >> n;                            // 输入，比如 200

    vector<bool> isPrime(n + 1, true);   // 标记数组，长度 n+1
    isPrime[0] = false;                  // 0 不是质数
    isPrime[1] = false;                  // 1 也不是质数

    // 埃氏筛法核心
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;      // 筛掉 i 的倍数
            }
        }
    }

    // 输出结果
    cout << "2 到 " << n << " 之间的质数有：";
    int count = 0;                       // 统计质数个数
    for (int num = 2; num <= n; num++) {
        if (isPrime[num]) {
            cout << num << " ";
            count++;
        }
    }
    cout << endl;
    cout << "一共 " << count << " 个质数。" << endl;
    return 0;
}

运行示例（n=50）：

请输入一个正整数 n：50
2 到 50 之间的质数有：2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 
一共 15 个质数。

埃氏筛法的小缺点

有些合数会被重复筛掉，比如 6 被 2 筛了一次，又被 3 筛了一次。虽然重复次数不多，但当 n 很大时（比如几百万），这种重复会拖慢速度。有没有办法让每个合数只被筛一次呢？线性筛法（也叫欧拉筛法） 就是专门来解决这个问题的，它能让每个合数只被它的最小质因数筛掉。

如果你对数学和算法感兴趣，下一个可以学习：

线性筛法：优化版本，更高效
质因数分解：把一个合数拆成几个质数的乘积
判断单个数是否为质数：用试除法，适用于小数字

埃氏筛法虽然简单，但它已经能解决很多实际问题了，比如生成质数表、密码学的基础操作。现在，你可以试试修改 n 的值，看看 1000 以内有多少个质数，或者用相同的方法找 10000 以内的质数。动手试一试吧！

埃氏筛法——找到所有小质数