素数筛

用于快速求出区间 $[1,n]$ 内的所有素数（质数）。包含两种经典的素数筛法：埃氏筛 与 欧拉筛(线性筛)。

---

原理

求素数的核心思路均建立在“合数必有质因子”这一性质之上，即通过已知的质数去标记其倍数为合数。两种筛法的核心区别在于标记合数的效率与是否存在重复标记。

1. 埃氏筛

埃氏筛的思想非常直观：从 $2$ 开始，按顺序遍历整数。每当遇到一个未经标记的数，它必定是质数；接着将该质数的所有倍数（大于其本身）标记为合数。

核心步骤与优化：

1. 初始化布尔数组 isPrime，默认所有数均视为质数。
2. 从 $i=2$ 开始遍历至 $\sqrt{n}$：
   • 若 isPrime[i] 为 true，说明 $i$ 为质数。
   • 从 $j=i^2$ 开始，以步长 $i$ 递增遍历（即 $i^2,i^2+i,i^2+2i,\cdots \le n$），将 isPrime[j] 标记为 false。
3. 优化点解释：为什么从 $i^2$ 开始标记？因为小于 $i^2$ 的倍数（如 $2i,3i,\dots ,(i-1)i$）已经在之前遍历更小的质数（如 $2,3,\dots$）时被提前标记过了。

缺陷分析：

埃氏筛存在重复标记的问题。例如，$12$ 会分别被质数 $2$（$2\times 6$）和质数 $3$（$3\times 4$）标记多次。这就导致其时间复杂度无法达到完美线性。

---

2. 欧拉筛（Sieve of Euler / 线性筛）

欧拉筛的核心目标是解决埃氏筛的重复标记问题，做到每一个合数只被其“最小质因子”筛掉一次，从而达到 $O(n)$ 的线性时间复杂度。

核心逻辑与 break 条件：

1. 维护一个标记数组 isPrime 和一个存储已找到质数的列表 primes。
2. 从 $i=2$ 到 $n$ 依次遍历：
   • 若 isPrime[i] 为 true，将 $i$ 加入 primes 列表。
   • 遍历已知质数列表中的质数 $p$：
     • 将 $i\times p$ 标记为合数。
     • 关键退出条件：若 i % p == 0，立即 break 终止当前内层循环。

（为什么 i % p == 0 必须 break）？：

• 当 i % p == 0 时，说明 $p$ 是 $i$ 的最小质因子。
• 如果继续使用下一个质数 $p_{\text{next}}$ 去标记 $i\times p_{\text{next}}$，则该数的最小质因子实际上是 $p$ 而不是 $p_{\text{next}}$。
• 因此，$i\times p_{\text{next}}$ 应该在后续遍历到 $i^{\prime }=\frac{i\times p_{\text{next}}}{p}$ 时，由质数 $p$ 负责筛除。
• 通过这个终止机制，确保了每个合数恰好只被其最小质因子访问并标记了一次。

---

代码实现

模板

//埃氏筛
std::vector<int> eratosthenesSieve(int n) {
    std::vector<bool> isPrime(n + 1, true);
    std::vector<int> primes;
    if (n < 2) return primes;

    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i <= n; ++i) {
        if (isPrime[i]) {
            // 从 i * i 开始标记，避免重复标记小于 i^2 的倍数
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    for (int i = 2; i <= n; ++i) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
    }
    return primes;
}

复杂度分析

名称	时间复杂度	空间复杂度	优缺点与特性
埃氏筛	$O(n\log \log n)$	$O(n)$	优点：逻辑直观，代码极简，常数极小。 缺点：存在多次重复标记合数的情况。
欧拉筛	$O(n)$	$O(n)$	优点：严格线性复杂度，适合顺便预处理积性函数。 缺点：需要额外开辟存储质数的数组，常数略大于埃氏筛。