🧹
埃氏筛与线性筛
用一个筛子，把 2 到 n 的质数全部筛出来
💡 打个比方
埃氏筛（Eratosthenes sieve）就像过筛子：把 2~30 的数字站成一排，先拿 2 当筛子，把所有 2 的倍数划掉；再拿 3 当筛子，划掉 3 的倍数；一直筛到 √n。没被划掉的，就是质数。
线性筛是升级版：规定每个合数只允许被它的最小质因子划一次。比如 12 只能被 2 划，不能 3 也来划一遍。谁也不重复干活，速度直接快到 O(n)。
两个筛子：埃氏筛 O(n log log n)——从 p×p 开始划 p 的倍数；线性筛 O(n)——维护质数表，每个合数恰好被最小质因子筛一次，关键在 i % primes[j] == 0 就 break。
🖼️ 大图看明白
📏 埃氏筛，只要 3 步
- 第 1 步：准备名单。开一个 bool 数组 isPrime[2..n]，先全部认为是质数（isPrime[0] = isPrime[1] = false）。
- 第 2 步：从 2 开始筛。对 i = 2 到 √n：如果 isPrime[i] 还是 true，就从 i × i 开始，把 i 的倍数 i×i、i×(i+1)、… 全部标记为合数（i×2、i×3 那些早被更小的质数划过了）。
- 第 3 步：收剩下的。筛完后，isPrime[i] 为 true 的 i 就是 2~n 里全部质数。
线性筛的关键一行：if (i % primes[j] == 0) break; 意思是"i 已经被质数 primes[j] 整除，那 i × primes[j] 之后轮到更小的 primes 来管"，保证每个合数只被最小质因子划一次。埃氏筛 O(n log log n)，线性筛 O(n)。
💻 C++ 怎么写
// 线性筛：O(n) 求出 2 ~ N 的所有质数
const int N = 1000000;
bool isComp[N]; // true 表示合数（被划掉）
int primes[N], cnt = 0; // 质数表
for (int i = 2; i <= N; i++) {
if (!isComp[i]) primes[cnt++] = i; // i 没被划，是质数
for (int j = 0; j < cnt; j++) {
if (1LL * i * primes[j] > N) break;
isComp[i * primes[j]] = true; // 用质数表划 i 的倍数
if (i % primes[j] == 0) break; // 最小质因子划完，停
}
}
cout << "质数个数: " << cnt << endl; // N=1e6 时是 78498
考点提醒：① 埃氏筛从 p×p 开始划，不是从 2p；② 线性筛 break 条件是 i % primes[j] == 0；③ 数组用 bool，开全局避免超栈；④ i × primes[j] 可能超 int，写 1LL 防溢出。
✋ 你来试试
题 1：埃氏筛为什么可以从 i × i 开始划，而不是从 2 × i 开始？
因为 i × 2、i × 3 … i × (i-1) 这些数，都含有比 i 更小的因子，早就被更小的质数划掉了。比如筛 5 时，10、15、20 分别早被 2、3、4（其实是 2）划掉了。从 i×i 开始，一个都不重复，省下大量功夫。
题 2：线性筛中，为什么 i % primes[j] == 0 时要 break？
为了保证每个合数只被它的最小质因子划一次。比如 12 = 3 × 4：当 i = 4、primes[j] = 3 时已经划了 12，如果继续，i = 6、primes[j] = 2 时又会划一次，重复劳动。break 的意思是："12 这种数以后由更小的质因子 2 来负责（6 × 2）"，谁负责、就只让谁划。
🎯 一句话记住：埃氏筛从 p×p 开始划倍数，O(n log log n)；线性筛 i % p == 0 就 break，每个合数只被最小质因子划一次，O(n) 出全部质数。