原始阶段：暴力试除法

根据质数的定义,我们很容易想到去验证是否存在某个数能整除$x$,枚举的范围$D = { i \mid i \in \mathbb{N},\ 2 \leq i \leq \lfloor \sqrt{x} \rfloor }$,其中 $\lfloor \sqrt{x} \rfloor$ 表示对 $\sqrt{x}$向下取整后的整数,$i \in \mathbb{N}$表示$i$属于自然数集.

为什么范围是2到$\sqrt{x}$?

假设 $x$ 有一个因数$d$满足$d > \sqrt{x}$且$d \in \mathbb{N}$，则必然存在另一个因数$k = \frac{x}{d}$ ，且 $k$ 满足 $k = \frac{x}{d} < \sqrt{x} $$($因为$d > \sqrt{x} \implies \frac{x}{d} < \sqrt{x} \text{ )}$

因此：

• 如果$x$不是质数，它至少有一个因数 小于或等于$\sqrt{x}$。
• 若在 $[2, \sqrt{x}]$ 内找不到因数，则 $x$一定是质数。

得代码:

bool isPrime(int x) {
    if (x <= 1) return false;
    for (int i = 2; i * i <= n; ++i) 
        if (n % i == 0) return false;
    return true;
}

第一步升级: 埃拉托斯特尼筛法

介绍

我们可以想到,如果一个数是质数,那么它的倍数一定是和数,我们可以一步一步地把所有和数标记下来,剩下的就是质数了.

于是就有这个逻辑

1. 初始化一个从$2$到$N$的连续整数列表。
2. 选取当前未被筛去的最小数$p$（初始为$2$），标记为质数。
3. 筛去p的所有倍数（从$p²$开始，如$2²=4$, $3²$=$9$等）。
4. 重复上述步骤，直到 $p² > N$。
5. 至此,剩余未被筛去的数均为质数。

视频理解

证明

那么,如何理解这个逻辑呢? 你可能有这些疑问:

Q:为什么所有的质数都会被留下来,而所有的和数都被筛掉了?

A:首先你要知道和数一定有质因子

假设存在一个合数 $a$ 没有质因子。则其所有因数（除 1 和它本身外）全是合数。设其中最小的合数因数为 $b$。根据合数的定义，$b$ 除了 1 和它本身外，还有一个因数 $c$，且 $c < b$ 并且 $c$ 是 $a$ 的因数。如果 $c$ 是质数，这与 $a$ 没有质因子相矛盾；如果 $c$ 是合数，这与 $b$ 是 $a$ 的最小合数因数相矛盾。因此，假设不成立，合数必定有质因子。

转载 知乎

设 $n$ 为合数，则必存在两个大于 1 的整数因子，使得

$$ n = p \times k, $$

其中 $p$ 为 $n$ 的最小质因数，$k$ 为另一个正整数因子。

设 $m$ 为不超过 $N$ 的任一合数，根据分解有

$$ m = p \times k, $$

其中 $p$ 是 $m$ 的最小质因数。为证明埃拉托斯特尼筛法能筛去 $m$，只需证明必有

$$ p \leq \sqrt{m}. $$

假设反之，若

$$ p > \sqrt{m}, $$

则由

$$ k = \frac{m}{p}, $$

可得

$$ k < \frac{m}{\sqrt{m}} = \sqrt{m}. $$

此时 $k < \sqrt{m} < p$。然而，若 $k < p$ 而 $p$ 为 $m$ 的最小质因数，则 $k$ 的分解必定涉及比 $p$ 更小的质因数，这与 $p$ 为最小质因数矛盾。因此必须有

$$ k \geq p. $$

由此得

$$ m = p \times k \geq p \times p = p^2, $$

即

$$ p^2 \leq m. $$

这意味着

$$ p \leq \sqrt{m}, $$

与前面假设的 $p > \sqrt{m}$ 矛盾。因此，假设不成立，即对任一合数 $m$，其最小质因数必满足

$$ p \leq \sqrt{m}. $$

在埃拉托斯特尼筛法中，算法先遍历区间 $[2, \sqrt{N}]$ 内的所有质数。当遍历到某一质数 $p$ 时，从 $p^2$ 开始，将 $p$ 的所有倍数（即形如 $p \times k$ 的数）依次标记为合数。考虑任一合数 $m \leq N$ 的分解 $m = p \times k$，由上面证明知有 $p \leq \sqrt{m} \leq \sqrt{N}$。因此，当算法遍历到 $p$ 时，必有

$$ p^2 \leq m, $$

进而 $m$ 将被 $p$ 的倍数标记而被筛去。

质数不被筛除的理由

设 $q$ 为质数。若 $q$ 被筛除，则存在某个质数 $p < q$ 使得 $q$ 为 $p$ 的倍数，即

$$ q = p \times k. $$

这意味着 $q$ 有除 1 与其自身以外的因子 $p$，与 $q$ 为质数的定义相矛盾。因此，质数在筛法中不会被标记和删除，从而最终得以保留。

Code

既然已经充分了解原理了,那让我们来写出代码吧

vector<bool> sieve(int n) {
    vector<bool> is_prime(n + 1, true);  // 初始化为全为质数
    is_prime[0] = is_prime[1] = false;   // 0和1不是质数
    
    for (int i = 2; (long long)i * i <= n; ++i) {  // 防止i*i溢出
        if (is_prime[i]) {  // 若i是质数，则筛去其倍数
            for (long long j = (long long)i * i; j <= n; j += i) {
                is_prime[j] = false;  // 标记为合数
            }
        }
    }
    return is_prime;
}

这段代码范围一个质数的标记数组,假设它的变量名是 $a$ ,即 $a[i]$ 表示 $i$ 是否为质数.

时间复杂度: $O(n \ \log \ \log n)$

空间优化

当 n 极大时（如 1e8），使用布尔数组（每个元素占 1 字节）需要约 100MB 内存。通过位运算可将内存压缩至 1/8：

vector<int> sieve_bit(int n) {
    vector<int> is_prime((n + 1) / 32 + 1, 0xFFFFFFFF);  // 初始化为全1
    is_prime[0] &= ~(3 << 0);  // 标记0和1为非质数
    
    for (int i = 2; i * i <= n; ++i) {
        if (is_prime[i >> 5] & (1 << (i & 31))) {  // 检查第i位是否为1
            for (int j = i * i; j <= n; j += i) {
                is_prime[j >> 5] &= ~(1 << (j & 31));  // 将第j位设为0
            }
        }
    }
    return is_prime;
}

更深一步的进阶: 欧拉筛法

介绍

我们发现埃式筛法虽然很高效,但是对于一些特殊的数会浪费掉一些资源,导致多次标记,欧拉筛再埃氏筛的基础上进行了优化:

算法步骤

1. 初始化：
   • 维护一个数组 is_prime[]，标记每个数是否为质数（初始全为 true）。
   • 维护一个列表 primes，动态存储已发现的质数。
2. 遍历每个数： 从 2 到 n 遍历每个整数 i：
   • 如果 i 是质数（is_prime[i] == true），将其加入 primes 列表。
   • 遍历当前已知的质数 p（从 primes 列表中取出）：
     • 标记合数 i * p 为非质数（is_prime[i * p] = false）。
     • 当 i % p == 0 时，停止对当前 i 的进一步筛除（关键步骤）。

可以看以下案例:

案例 1：合数 12

埃氏筛法中的重复标记过程

1. 当外层循环遍历到质数 i=2 时：
   • 标记 2 的倍数为合数：4, 6, 8, 10, 12, 14, ...
   • 第一次标记 12（12 = 2 × 6）。
2. 当外层循环遍历到质数 i=3 时：
   • 标记 3 的倍数为合数：9, 12, 15, 18, ...
   • 第二次标记 12（12 = 3 × 4）。

结果：12 被标记了 2 次。

欧拉筛法的处理

• 当外层循环 i=6 时，内层用已知质数 p=2 标记 6 × 2 = 12，随后因 6 % 2 == 0 终止循环。
• 后续质数 p=3 不会参与标记 12，因为循环已终止。 结果：12 仅被标记 1 次。

案例 2：合数 30

埃氏筛法中的重复标记过程

1. 当 i=2 时：
   • 标记 2 的倍数：4, 6, 8, 10, 12, ..., 30, ...
   • 第一次标记 30（30 = 2 × 15）。
2. 当 i=3 时：
   • 标记 3 的倍数：9, 12, 15, 18, 21, 24, 27, 30, ...
   • 第二次标记 30（30 = 3 × 10）。
3. 当 i=5 时：
   • 标记 5 的倍数：25, 30, 35, ...
   • 第三次标记 30（30 = 5 × 6）。

结果：30 被标记了 3 次。

理解

如视频动画,辅助您理解

Code

vector<int> euler_sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    vector<int> primes;
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) primes.push_back(i);  // i是质数，加入列表
        for (int p : primes) {                // 用已知质数筛除合数
            if (i * p > n) break;             // 超过范围则终止
            is_prime[i * p] = false;          // 标记合数i*p
            if (i % p == 0) break;            // 关键：保证每个合数由最小质因数筛去
        }
    }
    return primes;
}

时间复杂度：O(n)