计数质数

合数 = 某个质数的倍数。把 2 的倍数、3 的倍数、5 的倍数…… 全划掉,剩下的格子就是质数。这就是筛法。

准备 · 0~29 全标质数候选：绿色 = 暂时当成质数,灰色 = 已划掉。0 和 1 先划掉,剩下 2~29 都先当质数候选。

看 2 · 它是质数：从 2 开始扫。2 还活着,所以它是质数。接着把 2 的倍数(4、6、8…)一个个划掉。

划 2 的倍数 · 4：2 确认为质数(绿)。从 2×2=4 起划:4 被划掉。

划 2 的倍数 · 6：往后跳 2 格:6 划掉(刚划的 4 变灰)。

划 2 的倍数 · 8：再跳一步:8 划掉。第一行的偶数清完。

划 2 的倍数 · 10：进第二行,继续每隔 2 格划一个:10 划掉。

划 2 的倍数 · 12、14：接着划 12、14。

划 2 的倍数 · 16：再隔 2 格:16 划掉。

划 2 的倍数 · 18：再划 18。第二行的偶数也清完了。

划 2 的倍数 · 20、22：进第三行,继续划 20、22。

划 2 的倍数 · 24、26、28：再划 24、26、28。2 的倍数清完——所有偶数都没了。

比 p×p 小的倍数(像 2p)早被更小的质数划过了。划 3 的倍数时,6=2×3 已被 2 划掉,直接从 9=3×3 起步。

看 3 · 还活着：扫到 3,它还活着(2 的倍数里没有 3),所以 3 也是质数。轮到用 3 划倍数。

划 3 的倍数 · 9：3 确认为质数(绿)。从 3×3=9 起划:9 被划掉(6 早被 2 划过,跳过它)。

划 3 的倍数 · 15：每隔 3 往后:12 早被 2 划过(灰,跳过),15 划掉。

划 3 的倍数 · 21、27：继续每隔 3 划:21、27 划掉(18、24 早被 2 划过)。3 的倍数清完。

看 4 · 已是灰的：扫到 4,但它早被 2 划掉了(灰)。合数直接跳过,不用拿它去划倍数。

看 5 · 还活着：扫到 5,它还活着,是质数。从 5×5=25 起划倍数。

划 5 的倍数 · 25：5 确认为质数(绿)。从 25 起划:25 划掉(10、15、20 早被 2、3 划过)。

n=30 时 5×5=25<30 还要看,下一个质数 7 的 7×7=49 已 ≥30,不必再筛——大于 √n 的合数,小因子早被处理过了。剩下的全是质数。

筛完 · 数绿色格子：筛完!绿色的 2、3、5、7、11、13、17、19、23、29 就是小于 30 的全部质数,共 10 个。

雷区实演 · 误把 n 算进去：n=10 时表只到下标 9,绿色质数是 2、3、5、7 共 4 个。表压根不存 10——前提是表长开成 n 而不是 n+1。

边界三连：小 n 是高频坑:n ≤ 2 时答案都是 0。代码开头那句 if n 就是为它兜底。

面试追问：把复杂度的来历和「i*i / √n」两个剪枝讲透,是这题面试的加分点。