质数：试除 → 埃氏筛 → 线性筛

⚠ 而第二问那个「最小质因子」不是凑数的： 它是线性筛顺手白送的东西（第 7 步），埃氏筛却得再花一次力气才能给出来。 ★ 「题面多问一句」的第七次（第 35~40 章连着六次）—— 而这次多问的那一句，正好指着两种筛法真正的差别。

30 12
1 2 4 9 12 18 25 27 29 30 16 21

第一行 10        （2 3 5 7 11 13 17 19 23 29）
第二行 0 2 2 3 2 2 5 3 29 2 2 3
第三行 29

一个个对：1 → 0（题面规定）、2 → 2（质数，最小质因子是自己）、 4 → 2、9 → 3、25 → 5、29 → 29、30 → 2。

三处特意安排：

• 询问里有 x = 1 —— 卡 wrongOne；
• 询问里有 4、9、25、16 这些完全平方数 —— 卡 wrongSq；
• n = 30 是合数 —— 卡 wrongEnd（埃氏筛内层写成 j < n 时，30 自己没被划掉）。

⚠ 而第六个（wrongEmpty）在这组数据上一个字都不错 —— 它只在 n = 1 时现形，这一点第 9 步会算给你看。

如果 x = a × b 且 a ≤ b，那么 a ≤ √x。 所以只要 √x 以内没有约数，就再也不会有了。 一句话的事，可它是这一章所有次数的起点。

⚠ 而它作为标准答案有一个好处：思路和筛法完全不同 —— 筛法是「从质数出发去划掉合数」，它是「对每个数单独审问一遍」 （第 9、15 章那条规矩：标准答案最好换个想法写）。

比 i² 小的 i 的倍数是 k·i（k < i），它一定有一个比 i 小的质因子 —— 那个质因子在更早的一轮里就已经把它划掉了。所以 2i … (i−1)i 全是白划。

⚠ 但这只是个常数级的省事，改变不了复杂度：

点「运行 ▶」看结果

第 5 步那张表会量出来：两者只差 1.33 倍（而线性筛差的是 2.4 倍）。

试除 / 埃氏筛（2i 起）/ 埃氏筛（i·i 起）/ 线性筛 / 线性筛忘了 break —— 五份代码的输出逐字节相同（check:viz 里 300 轮钉着）。

第 36 章立的「随机对拍第四个盲区」，第 37~40 章各一次现场，这是第六次。

点「运行 ▶」看结果

★★ 这张表里有两条等号，都不是「大约」：

① 线性筛划的次数 = 合数的个数。 10⁵ 以内有 9 592 个质数、90 407 个合数 —— 而线性筛正好划了 90 407 次。

每个合数被划掉一次，一个不多一个不少。这就是「线性」两个字的全部含义。

② ★★★「线性筛忘了 break」划的次数，恰好等于「埃氏筛从 i·i 起」。 两个 n 上都一字不差 —— 而且这是能证的，因为两边划的是同一批数对：

• 埃氏筛从 i·i 起：对每个质数 p 划 k·p（k ≥ p）⇒ 数对 {(k, p) : p 质数, p ≤ k, kp ≤ n}；
• 线性筛忘了 break：对每个 i 遍历已经找到的质数（也就是所有 p ≤ i）⇒ 数对 {(i, p) : p 质数, p ≤ i, ip ≤ n}。

两个集合一模一样。 ∎

★ 所以「忘了 break」不是「退化到埃氏筛那个量级」，是一步不差地就是埃氏筛。

for (int p : primes) {
    if ((long long)i * p > n) break;
    minp[i * p] = p;              // 用 p 去划掉 i*p
    if (i % p == 0) break;        // ★★ 全章的灵魂
}

① 每个合数都被划到了。 设合数 c 的最小质因子是 p，写 c = i·p（i = c/p）。 因为 p 是 c 的最小质因子，所以 i 的每个质因子都 ≥ p —— 于是内层走到 p 的时候还没 break（前面那些质数都比 p 小、都不整除 i），c 就在这一步被划掉了。

② 每个合数只被划一次。 内层用 p 去划 i·p 时，那句 break 保证了 p ≤ i 的最小质因子， 于是 p 一定是 i·p 的最小质因子。 而一个合数的最小质因子只有一个、对应的 i = c/p 也只有一个 —— (i, p) 这一对是唯一的，所以只会被划一次。∎

★ 那句 break 干的事，一句话说清：一旦 p 整除 i，就不许再往大的质数走。 再走下去，划的那个 i·p' 的最小质因子就不是 p' 了（而是 p），那就重复了。

⇒ 总划掉次数 = 合数个数 = O(n)。

线性筛划掉 i·p 的时候，划它的那个 p 正好就是它的最小质因子 —— 所以只要把 minp[i*p] = p 记下来，minp[] 就自动成型了。

有了它，分解质因数从 O(√x) 掉到 O(log x)：一路除最小质因子就行。

⚠ 对照埃氏筛：它只记了「是不是合数」，要拿最小质因子还得再试除一遍（见 erat.cpp）。

★★ 这才是线性筛真正比埃氏筛强的地方 —— 不是快，是它顺手多给了一样东西。 （第 10 步会看到：论速度，它并没有赢。）

★★ 最后两条要的不是值域、不是规模、也不是结构，而是「你有没有把那个特定的数塞进去」。 而随机撞上它们的概率是 1/n 和 1/50 —— n 一大就全没了。

这是第 38 章那条「题面多问一句兜的是随机数据碰不到的那个边界」的另一张脸： 这一次不是题面的问题，是生成器的问题。

① ★★★ 档位 5 和 6 是这一章最干净的一对：

n 只取质数 → wrongEnd 0 / 300；n 只取合数 → 300 / 300。 因为那个 bug 是「埃氏筛少划了 n 自己」—— n 是质数的时候，它本来就不该被划掉。 一端把 bug 变成了一份完全正确的程序，另一端让它必现。 （第 38 章「n 是不是 2 的幂」那次的第三次现场。）

② ⚠⚠ 档位 4 是这一章最该警惕的一档。 把 n 放大到 3000：三列直接满分 300 —— 看着是全表最好的一档。 可 wrongOne 掉到了 1 / 300。 理由很直白：随机询问撞到 x = 1 的概率是 1/n —— n 从 50 涨到 3000，这个概率就掉了六十倍。

★★ 规模一大，边界就碰不到了。

③ ⚠ 而 wrongEmpty 在前八档里有七档是 0。 n = 1 在 [1,50] 里只占 1/50，靠运气等不来 —— 只能专门造。

① 「专门造 n = 1」的账要老实写：它把别的列全拉低了。 291 → 253、255 → 211、291 → 253 —— 因为 12% 的轮次里 n = 1，那些轮次什么都测不到。

★ 但它是唯一让 wrongEmpty 非 0 的旋钮（0 → 37）。 把 0 变成非 0，掉多少抓获率都划算（第 30 章那条）—— 0 / 300 是「完全测不到」，37 / 300 是「第 5 轮就抓住」，这两者不是量的差别。

② ★★ 而「放大 n」这一处，单独加是灾难、组合起来却是最好的。 单独看（档位 4）它把 wrongOne 打成 1 / 300； 可配上「询问里专门塞 1」之后（档位 10），wrongOne 有 228， 同时 Minp 从 175 涨到 259、End 从 181 涨到 228。

★★ 第 32、35、36、37、39、40 章那条「调优不可加」的又一次 —— 而这次是正面的那一种： 一处单独看是负分的改动，和另一处配起来就成立了。 道理也说得清：放大 n 让「筛」这件事本身更难，而塞 1 把边界补了回来 —— 两处管的根本不是同一件事。

③ 对照档 12 量的是「塞 1」值多少：wrongOne 49 → 228，接近五倍。