埃氏筛入门

1. 算法简介

埃氏筛是一种简单且古老的求取不超过自然数 (n) 的所有素数（质数）的算法。由古希腊数学家埃拉托斯特尼提出，其核心思想是逐步剔除合数，最终留下的即为素数。

2. 算法原理与步骤

基本思想：一个素数的倍数一定是合数。从最小的素数 2 开始，将其所有倍数标记为合数，然后找到下一个未被标记的数（即为下一个素数），重复此过程。

详细步骤（求 2 到 n 的所有素数）

1. 创建一个长度为 (n+1) 的布尔数组 is_prime，初始全部设为 true（假设所有数都是素数），并将 is_prime[0] = is_prime[1] = false（0 和 1 不是素数）。
2. 从 (p = 2) 开始循环：
   • 如果 is_prime[p] 为 true，则说明 (p) 是素数：
     • 将 (p) 的所有倍数$(2p, 3p, 4p, \dots)$标记为 false（从 $(p^2)$ 开始标记可优化）。
   • 否则，直接跳过。
3. 令 (p) 增加 1，重复步骤 2，直到 $(p^2 > n)$ 为止（因为若 $(p > \sqrt{n})$且未被标记，则其倍数 $(p^2 > n)$已经处理过）。
4. 遍历数组，所有值为 true 的下标即为素数。

优化点：从$(p^2)$开始标记

由于 (p) 的倍数$(k \cdot p)$（其中 (k < p)）一定已经被更小的素数标记过了，因此只需从$(p^2)$开始标记。这大幅减少了重复标记次数。

3. 代码实现

bool is_prime[10005] = {};
for(int i = 2; i <= 10000; i++) is_prime[i] = true;

for (int p = 2; p * p <= n; p++) {
    if (is_prime[p]) {
        for (int t = p * p; t <= n; t += p) {
            is_prime[t] = false;
        }
    }
}