埃氏筛

1. 问题的引入与比喻

假设现在有一个任务：找出从 $2$ 到 $N$ 之间的所有素数（质数）。

最朴素的想法（试除法）：
就像是你要检查一筐苹果（数字 $2$ 到 $N$）里哪些是“纯正的好苹果”（素数）。你拿起一个数字，然后从 $2$ 尝试除到 $\sqrt{N}$，看看能不能整除。这种方法虽然直观，但是当 $N$ 很大时，你检查每一个苹果花费的时间太长了，效率极低。

筛法的比喻（排除法）：
与其去证明哪些苹果是“好苹果”，不如我们把“坏苹果”（合数）全部挑出来扔掉，剩下的自然就全是好苹果了。这就是“筛法”的核心逻辑。

---

2. 埃氏筛的核心思想

埃氏筛的规则非常简单，可以用一句大白话概括：一个素数的各个倍数，一定不是素数（一定是合数）。

具体操作步骤：

1. 把 $2$ 到 $N$ 所有的数字写下来，初始时假定它们全是素数（白纸状态）。
2. 从第一个数字 $2$ 开始，$2$ 是素数，然后我们拿起大印章，把 $2$ 所有的倍数（$4,6,8,10\dots$）全部盖上“黑戳”（标记为合数）。
3. 接着往后看，找到下一个没有被盖黑戳的数字（即 $3$），它就是素数。接着把 $3$ 的所有倍数（$6,9,12\dots$）盖上黑戳。
4. 一直重复这个过程，直到找完 $N$ 范围内的所有数字。

---

3. 字符画动态演示

我们以 $N=10$ 为例，用字符画看看埃氏筛是如何工作的：

初始状态：（假设大家都是素数，用 [ ] 表示）

数字:   2   3   4   5   6   7   8   9  10
状态:  [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] 

第一步： 找到未标记的 $2$，它是素数。筛掉 $2$ 的倍数 ($4,6,8,10$)，打上 [X]。

当前素数: 2
数字:   2   3   4   5   6   7   8   9  10
状态:  [ ] [ ] [X] [ ] [X] [ ] [X] [ ] [X] 

第二步： 找到下一个未标记的 $3$，它是素数。筛掉 $3$ 的倍数 ($6,9$)。（注意 $6$ 之前已经被 $2$ 筛过了，这里再次被盖戳）

当前素数: 3
数字:   2   3   4   5   6   7   8   9  10
状态:  [ ] [ ] [X] [ ] [X] [ ] [X] [X] [X] 

第三步及以后： 下一个未标记的是 $5$，筛掉 $5$ 的倍数（$10$ 已经被标记）；下一个是 $7$，筛掉 $7$ 的倍数…
最终剩下没有 [X] 标记的数字：2, 3, 5, 7，这就是我们找出的素数。

---

4. 埃氏筛 C++ 演示 Demo

下面是使用 C++ 编写的埃氏筛模板代码：

#include <iostream>
#include <vector>

// 埃氏筛函数：寻找从 2 到 n 的所有素数
void eratosthenesSieve(int n) {
    // is_prime 数组用来记录是否是素数
    // true 表示是素数（未被盖戳），false 表示是合数（已被盖黑戳）
    // 初始时默认全部为 true
    std::vector<bool> is_prime(n + 1, true);
    
    // 0 和 1 不是素数，手动标记
    is_prime[0] = is_prime[1] = false;

    // 存放筛选出的素数
    std::vector<int> primes;

    // 从 2 开始遍历到 n
    for (int i = 2; i <= n; ++i) {
        // 如果当前数字是素数（没有被前面的数字盖黑戳）
        if (is_prime[i]) {
            primes.push_back(i); // 收集这个素数
            
            // 拿起大印章，把 i 的所有倍数都标记为合数
            // 优化点：可以从 i * i 开始标记，因为比起 i 小的倍数（如 2*i, 3*i）
            // 早就被之前的数字 2, 3 筛过了。为了防止溢出使用 long long
            for (long long j = (long long)i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }

    // 打印结果展示
    std::cout << "在 2 到 " << n << " 之间的素数有: \n";
    for (int p : primes) {
        std::cout << p << " ";
    }
    std::cout << "\n共计: " << primes.size() << " 个\n";
}

int main() {
    int N = 50; // 测试寻找 50 以内的素数
    eratosthenesSieve(N);
    return 0;
}

---

5. 发现问题

你可以观察一下刚才的字符画演示以及代码逻辑。虽然埃氏筛的效率已经很高，时间复杂度约为 $O(N\log \log N)$，但它存在一个明显的浪费现象。

以数字 12 为例：

• 当素数是 $2$ 时，会把 $2\times 6=12$ 筛掉一次（盖一次黑戳）。
• 当素数是 $3$ 时，会把 $3\times 4=12$ 又筛掉一次（再盖一次黑戳）。

一个数字如果含有多个不同的素因子，它就会被重复盖戳多次。当 $N$ 达到千万级别甚至上亿时，这种重复标记会浪费大量的时间。

---

欧拉筛

在上一节中，我们观察到埃氏筛存在“重复盖戳”的问题（例如数字 $12$ 会被 $2$ 和 $3$ 反复标记）。当数据范围很大时，这种重复操作会拖慢程序的运行速度。

为了解决这个问题，欧拉筛（Euler’s Sieve），也被称为线性筛，应运而生。它的时间复杂度降到了完美的 $O(N)$，也就是每个数字只会被处理一次。

1. 欧拉筛的核心思想：唯一负责人制度

如果说埃氏筛是“所有素数去寻找自己的倍数”，那么欧拉筛的核心思想就是建立严格的“唯一负责人制度”。

通俗的比喻：
我们要淘汰掉所有的“坏苹果”（合数）。为了避免多个检查员（素数）重复检查同一个坏苹果，我们制定了一条铁律：每一个合数，只能被它最小的那个“素数检查员”淘汰。

举个例子，合数 $12$ 的质因数有 $2$ 和 $3$。

• 在埃氏筛中，$2$ 觉得 $12$ 是它的倍数，盖了个戳；$3$ 觉得 $12$ 也是它的倍数，又盖了个戳。
• 在欧拉筛中，$12$ 最小的质因数是 $2$，所以 $12$ 只能由 $2$ 这个检查员来盖戳淘汰，$3$ 没有权限去碰 $12$。

---

2. “关键刹车”机制（演示与字符画）

欧拉筛是怎么做到让每个合数只被最小质因数标记的呢？核心在于一行代码：if (i % p == 0) break;。我们称之为“关键刹车”。

我们用字符画来模拟一下 $N=12$ 时，运行到 $i=4$ 和 $i=6$ 的情况。假设此时我们已经收集到了素数 primes = [2, 3]。

场景一：当 $i=4$ 时
欧拉筛会用当前的 $i$ 去乘以已经找到的素数表。

当前 i = 4, 已知素数表 [2, 3]

1. 取出素数 2：计算 4 * 2 = 8。
   标记 8 为合数。 (8 的最小质因数是 2，正确)
   
2. 触发检查：4 % 2 == 0 成立吗？
   成立！因为 4 可以被 2 整除。
   触发【关键刹车】，停止后续的相乘！

为什么要刹车？
如果不刹车，下一步计算 $4\times 3=12$。虽然 $12$ 是合数，但 $12$ 的最小质因数是 $2$，而不是 $3$。如果现在用 $3$ 把 $12$ 划掉，就违反了“唯一负责人制度”。

场景二：把 12 留给真正该负责的 $i$
当程序运行到 $i=6$ 时：

当前 i = 6, 已知素数表 [2, 3, 5]

1. 取出素数 2：计算 6 * 2 = 12。
   标记 12 为合数。(12 的最小质因数是 2，正确！)
   
2. 触发检查：6 % 2 == 0 成立！
   触发【关键刹车】，停止相乘。

你看，数字 $12$ 最终是在 $i=6$ 且素数为 $2$ 的时候被标记的，完美避免了重复！

---

3. 欧拉筛 C++ 演示 Demo

下面是欧拉筛的标准 C++ 模板。在算法竞赛（例如蓝桥杯）中，如果需要预处理大量素数，这套模板是必背的基础。

#include <iostream>
#include <vector>

// 欧拉筛函数：寻找从 2 到 n 的所有素数
void eulerSieve(int n) {
    // is_prime[i] 记录 i 是否为素数，初始全部假定为 true
    std::vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false; // 0 和 1 不是素数
    
    // primes 数组用于按顺序存储找到的素数
    std::vector<int> primes;

    // 外层循环遍历 2 到 n 的每一个数
    for (int i = 2; i <= n; ++i) {
        // 1. 如果当前数 i 还没被前面的数淘汰，那它就是素数
        if (is_prime[i]) {
            primes.push_back(i); 
        }

        // 2. 让当前数 i 依次乘以已经收集到的素数
        for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
            // 合数 i * primes[j] 被淘汰
            is_prime[i * primes[j]] = false;

            // 3. 【关键刹车】保证每个合数只被其最小质因数淘汰
            if (i % primes[j] == 0) {
                break; 
            }
        }
    }

    // 打印结果展示（仅展示前几个和总数，避免输出过多）
    std::cout << "在 2 到 " << n << " 之间的素数有: \n";
    for (int k = 0; k < primes.size() && k < 10; ++k) {
        std::cout << primes[k] << " ";
    }
    std::cout << "... \n共计: " << primes.size() << " 个\n";
}

int main() {
    int N = 50; 
    eulerSieve(N);
    return 0;
}

---

4. 总结与进阶展望

埃氏筛 vs 欧拉筛：

• 埃氏筛： 用素数去筛倍数，一个合数有几个质因数，就会被筛几次。
• 欧拉筛： 让每一个数（无论素数还是合数）去乘以已知的素数，通过 i % p == 0 的刹车机制，确保合数只被最小质因数筛掉一次，实现严格的 $O(N)$ 线性时间复杂度。

---

总结

1. 筛法核心对比总结

我们用一张表格来直观对比这两种筛法的差异：

特性	埃氏筛 (Eratosthenes)	欧拉筛 (Euler/线性筛)
核心思想	素数主动出击，筛掉自己的所有倍数	唯一负责人制度：合数只被最小质因数筛掉
关键代码	for(j = i*i; j <= n; j += i)	if (i % primes[j] == 0) break; (关键刹车)
时间复杂度	$O(N\log \log N)$	$O(N)$ （严格线性时间）
重复标记	存在（如 12 会被 2 和 3 重复盖戳）	完美避免（12 只会在 i=6 时被 2 盖戳）

2. 关键知识点备忘

• 埃氏筛的本质是“排除法”：我们不去证明谁是素数，而是把合数全扔掉。它的代码更简短，在数据范围不是极端大（比如 $10^6$ 以内）的时候，它的速度和欧拉筛相差无几，完全可以直接手写。
• 欧拉筛的灵魂是“刹车”：if (i % p == 0)。当这句话成立时，意味着当前的质数 $p$ 已经在数字 $i$ 的肚子里了。如果此时不刹车，下一个质数去乘 $i$ 得到的合数，其最小质因数依然是 $p$ 而不是那个新的质数，这就违背了“最小质因数负责制”。