算法基础之埃氏筛：从古老智慧到现代优化的素数筛法#

2.1 核心思想：一个朴素而深刻的事实#

埃氏筛的核心思想极其简洁：一个素数的倍数一定不是素数。具体来说，如果我们从最小的素数 2 开始，把 2 的所有倍数都标记为合数，然后找到下一个未被标记的数（它就是素数），再将其所有倍数标记为合数，如此反复，最终剩下的未被标记的数就是素数。

用一个生活化的比喻来帮助理解：就像筛选班级里的”好学生”，先假设所有人都是好学生（质数），然后从第一个人开始，把每个”坏学生”（合数）逐个找出来标注，最后剩下的就是真正的好学生（质数）。

2.2 筛选过程可视化#

以筛选 1 到 30 之间的素数为例，整个过程如下：

1
初始状态（假设所有 ≥2 的数都是素数，用□表示，■表示合数）：
2

3
        2   3   4   5   6   7   8   9  10
4
       □   □   □   □   □   □   □   □   □
5

6
       11  12  13  14  15  16  17  18  19  20
7
       □   □   □   □   □   □   □   □   □   □
8

9
       21  22  23  24  25  26  27  28  29  30
10
       □   □   □   □   □   □   □   □   □   □

第一轮（用 2 筛）：2 是素数，从 $(2 \times 2 = 4)$ 开始，把 2 的倍数（4、6、8、…）全部标记为合数：

1
被筛除：4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30

第二轮（用 3 筛）：3 是素数，从 $(3 \times 3 = 9)$ 开始，把 3 的倍数（9、12、15、…）全部标记为合数。注意，12 已经被 2 筛过了，这里会重复标记——这就是埃氏筛的缺陷所在：

1
被筛除：9, 12(重复), 15, 18(重复), 21, 24(重复), 27, 30(重复)

第三轮（用 5 筛）：5 是素数，从 $(5 \times 5 = 25)$ 开始筛选：

1
被筛除：25, 30(重复)

终止条件：此时 $(7 \times 7 = 49 > 30)$，所以 7 及更大的素数无需再筛——因为任何 ≤30 的合数，其最小质因子一定 ≤ $(\sqrt{30})$，已经被之前的素数筛过了。

最终未被标记的数即为素数：

1
2  3  5  7  11  13  17  19  23  29  ← 1~30 之间的全部素数

2.3 关键优化：为何从 (i^2) 开始？#

细心的读者可能注意到，上面筛选时并不是从 $(i \times 2)$ 开始，而是从 $(i \times i)$（即 (i^2)）开始。这是因为：当一个素数 (p) 的倍数 $(p \times k)$ 中 (k < p) 时，(k) 一定已经被更小的素数筛过了。例如，筛 5 时，$(5 \times 2 = 10)$ 和 $(5 \times 3 = 15)$ 已经被 2 和 3 分别筛除，所以只需从 $(5 \times 5 = 25)$ 开始。这一优化极大地减少了重复操作，也是算法能拥有优秀时间复杂度的关键。

3.1 基础版本#

以下是最简洁的埃氏筛 C++ 实现：

1
const int MAXN = 1e6 + 5;
2
bool is_prime[MAXN];  // true 表示素数，false 表示合数
3

4
void eratosthenes(int n) {
5
    // 初始化：0 和 1 不是素数，其余默认为素数
6
    is_prime[0] = is_prime[1] = false;
7
    for (int i = 2; i <= n; i++) {
8
        is_prime[i] = true;
9
    }
10

11
    for (int i = 2; i * i <= n; i++) {
12
        if (is_prime[i]) {
13
            // 从 i*i 开始，步长为 i，标记所有 i 的倍数
14
            for (int j = i * i; j <= n; j += i) {
15
                is_prime[j] = false;
16
            }
17
        }
18
    }
19
}

3.2 常用版本（边筛边收集素数）#

在实际应用中，我们通常希望同时获得素数列表。以下版本在筛选的同时将素数收集起来，并采用 bitset 优化内存：

1
const int MAXN = 1e8 + 10;
2
bitset<MAXN> is_prime;   // 使用 bitset 代替 bool 数组，节省 8 倍空间
3
int primes[MAXN];         // 存储所有素数
4
int cnt = 0;              // 素数个数
5

6
void get_primes(int n) {
7
    is_prime.set();        // 全部置为 true
8
    is_prime[0] = is_prime[1] = false;  // 0 和 1 不是素数
9

10
    for (int i = 2; i <= n; i++) {
11
        if (is_prime[i]) {
12
            primes[++cnt] = i;  // 发现素数，记录下来
13
        }
14
        // 注意：这里筛倍数时仍然从 i*i 开始
15
        // 但外层循环遍历到 n 而不是 sqrt(n)，是为了顺便收集素数
16
        for (int j = i * i; j <= n; j += i) {
17
            is_prime[j] = false;
18
        }
19
    }
20
}

需要注意的是，这个版本中筛除操作仍然从 i*i 开始，当 i 较大时 i*i 可能超过 n，此时内层循环自动跳过，不影响正确性。

4.1 直观分析#

埃氏筛的两层循环看起来像 (O(n^2))，但实际远非如此。对于每个素数 (p)，我们标记的次数大约是 (n/p) 次。因此总操作次数约为：

$\sum_{p \leq n,\ p\text{ 为素数}} \frac{n}{p} = n \cdot \sum_{p \leq n} \frac{1}{p}$

根据数论中的重要结论，素数倒数和渐近于 (\log \log n)：

$\sum_{p \leq n} \frac{1}{p} \approx \log \log n + M$

其中 (M) 为 Meissel–Mertens 常数（约 0.2615）。由此可得：

$T(n) \approx n \cdot \log \log n$

4.2 时间复杂度结论#

埃氏筛的时间复杂度为 $(O(n \log \log n))$，这在理论上已被严格证明。当 (n = 10^6) 时，$(\log \log n \approx 2.5)$，意味着实际常数非常小；当 $(n = 10^9)$ 时，$(\log \log n \approx 3.0)$，增长极其缓慢。因此在实际应用中，埃氏筛的性能几乎接近于线性，远优于朴素方法的 $(O(n\sqrt{n}))$。

4.3 空间复杂度#

埃氏筛使用一个长度为 (n+1) 的布尔数组来标记每个数的素数状态，空间复杂度为 $(O(n))$。对于 $(n = 10^8)$ 的范围，使用 bool 数组约需 100MB 内存，而换用 bitset 后仅需约 12.5MB，大大降低了对内存的要求。

5.1 从 i*i 开始筛（已在基础版本中体现）#

这是最基础也最重要的优化。将内层循环的起点从 2*i 改为 i*i，可以避免对已经被更小素数标记过的数进行重复操作，能减少约 30% 的无效标记。

5.2 只筛奇数#

除 2 以外，所有偶数都不是素数。因此可以预先排除偶数，将存储需求和操作次数减半：

1
void sieve_odd_only(int n) {
2
    is_prime[2] = true;
3
    // 只处理奇数，索引映射：下标 i 对应数字 2*i+1
4
    for (int i = 3; i <= n; i += 2) {
5
        is_prime[i] = true;
6
    }
7
    for (int i = 3; i * i <= n; i += 2) {
8
        if (is_prime[i]) {
9
            // 步长为 2*i，因为 i 是奇数，i*i 是奇数
10
            // 加 i 后变为偶数（已排除），再加 i 才回到奇数
11
            for (int j = i * i; j <= n; j += 2 * i) {
12
                is_prime[j] = false;
13
            }
14
        }
15
    }
16
}

这一优化在实测中可将运行时间缩短约 40%。

5.3 使用 bitset 替代 bool 数组#

C++ 标准库中的 bitset 将每个布尔值压缩为 1 个比特（而非 1 个字节），使内存占用减少为原来的 1/8。更重要的是，更紧凑的内存布局带来了更好的缓存命中率。

有趣的是，测试表明：时间复杂度 $(O(n \log \log n))$ 的埃氏筛在使用 bitset 优化后，其实际运行速度甚至能超过时间复杂度 (O(n)) 的欧拉筛。这是因为埃氏筛的常数因子较小，且 bitset 对缓存更友好。

5.4 分块 / 区间筛法#

当需要筛选的范围非常大（如 $(n \geq 10^{12})$）而内存不足以容纳整个数组时，可以采用分块策略：先用小范围的埃氏筛筛出所有 $(\leq \sqrt{n})$的素数（”基础素数”），然后将 ([L, R]) 分成若干块，逐块用基础素数进行筛选。每块大小可根据内存限制灵活设定，这一技巧常用于高难度算法竞赛题目。

6.1 埃氏筛的缺陷#

埃氏筛的一个明显问题是重复标记：同一个合数可能被多个素因数重复筛除。例如合数 12 既会被 2 筛除$(2 \times 6 = 12)$，又会被 3 筛除$(3 \times 4 = 12)$。合数 39 会被 3 和 13 两数重复筛去。当 (n) 很大时，这种重复带来的额外开销不可忽视。

6.2 欧拉筛的核心改进#

欧拉筛（也称线性筛）基于一个关键思想：每个合数只被它最小的质因数筛掉。它能确保每个合数恰好被标记一次，从而实现严格的 (O(n)) 线性时间复杂度。

1
// 欧拉筛（线性筛）核心代码
2
void euler_sieve(int n) {
3
    for (int i = 2; i <= n; i++) {
4
        if (!is_prime[i]) primes[++cnt] = i; // 初始化时 is_prime 数组全部为 false，表示“暂时都假设是素数”。
5
        for (int j = 1; j <= cnt && i * primes[j] <= n; j++) {
6
            is_prime[i * primes[j]] = true; // 标记为合数
7
            if (i % primes[j] == 0) break;  // 关键：保证最小质因数
8
        }
9
    }
10
}

其中 if (i % primes[j] == 0) break; 这一行是关键：当 primes[j] 是 i 的最小质因数时立即跳出循环，确保了后续标记的合数都以当前质数为最小质因数，从而杜绝重复。

6.3 对比总结#

有意思的是，在实际测试中，由于埃氏筛没有取模运算，常数因子更小，配合 bitset 优化后运行速度甚至能反超欧拉筛。因此，在实际工程和竞赛中，应根据具体需求选择合适的算法，不必盲目追求”理论上最优”。