线性筛（欧拉筛）

线性筛是埃氏筛的升级版。回忆一下埃氏筛：对每个素数 p，把它的所有倍数 p², 2p², 3p²… 划掉。这样同一个合数会被多个不同的素数反复划（比如 12 被 2 划过又被 3 划），是 O(n log log n)，不是真正的线性。

线性筛的核心承诺：每个合数只被它的最小质因子划掉一次，做到 O(n)。

关键技巧：那个 break

for (int i = 2; i <= n; ++i) {
  if (spf[i] == 0) { spf[i] = i; primes.push_back(i); }
  for (int p : primes) {
    if (i * p > n) break;
    spf[i * p] = p;
    if (i % p == 0) break;   // 关键
  }
}

枚举 i，枚举已知素数 p（从小到大），把 i × p 划掉，并记 spf[i*p] = p。

为什么 i % p == 0 时要 break？因为这意味着 p 是 i 的最小质因子。如果继续乘下一个更大的素数 p'，那么 i × p' 的最小质因子还是 p（藏在 i 里），而不是 p'。这一对组合应该等到将来 i' = i / p × p' 时再被划掉。否则就会重复 — 线性性就破坏了。

同时拿到”最小质因子表” (SPF)

线性筛的副产品 spf[] 是 每个数的最小质因子。有了它可以 O(log k) 分解任意 k：

while (k > 1) { print(spf[k]); k /= spf[k]; }

这在数论题里特别好用。

复杂度

• 时间：O(n) — 每个合数恰好被划一次
• 空间：O(n) — spf 表

在动画里看什么

• 绿色：已确认的素数
• 红色高亮：当前正在划的合数 i × p
• 每个合数下方的 ÷p 标记表示它的最小质因子是谁
• 当 i % p == 0 触发 break 时，下方提示框会解释为什么必须停 — 这是线性筛的灵魂