统计小于n的质数个数。最朴素的做法是对每个数试除到√x，整体O(n√n)。n = 10⁶时要跑约10⁹次除法，慢得不能忍。

换个思路：与其一个个判断“谁是质数”，不如把“谁不是质数”批量划掉。

• 2是质数 → 划掉4, 6, 8, 10, …
• 3是质数 → 划掉9, 15, 21, …（6已被划过，可跳过）
• 4已划掉 → 跳过
• 5是质数 → 划掉25, 35, …

这就是埃拉托斯特尼筛法，公元前3世纪就被发明出来了。

但埃氏筛有个瑕疵：合数会被重复划掉（30被2、3、5各划一次）。能不能让每个合数只被划一次？能——这就是欧拉筛（线性筛），复杂度从O(nloglogn) 降到O(n)。

今天的主线就是这三次提速。而在结尾，我会给你一组实测数据，证明理论最优的欧拉筛在Python里反而最慢——这是本周第二次遇到“理论更优、实测更慢”。

---

📦 题目速览（30秒读懂）

题目1：计数质数（LC.204）

返回所有小于n的质数数量。

示例： n = 10 → 4（2,3,5,7）；n = 0 → 0
约束： n ≤ 5×10⁶。

延伸：丑数（LC.263 / LC.264）

LC.263：判断n是否为丑数（质因子只含2、3、5）。
LC.264：返回第n个丑数。n = 10 → 12

丑数严格说不是筛法，而是筛法的对偶形态——筛法是“排除合数”，丑数是“正向生成”。

---

🧠 核心思路：三次提速

第一级：试除法O(n√n)

对每个x试除i从2到√x（若x有大于√x的因子，必有对应的小于√x 的因子）。

n = 10⁶时约10⁹次运算——不可用，但它是理解后两种方法的基线。

第二级：埃氏筛O(nloglogn)

核心：找到质数就划掉它的所有倍数。

两个关键优化：

1. 从i*i开始划，而不是2*i——更小的倍数已被之前的质数划掉
2. 外层只需到√n——任何合数 ≤ n 必有因子 ≤ √n

复杂度O(nloglogn) 来自Σ n/p（对所有质数p求和），由素数定理的推论Σ 1/p ≈ loglogn得到。它非常接近线性。

埃氏筛的瑕疵：合数会被重复划掉。30 = 2×15 = 3×10 = 5×6，被划3次。这就是它没能做到O(n) 的原因。

第三级：欧拉筛（线性筛）O(n)

核心思想：让每个合数只被它的最小质因子划掉一次。

for p in primes:
    if i * p >= n: break
    is_comp[i * p] = True
    if i % p == 0: break      # 关键的一行

为什么这个break是对的？
设p是第一个整除i的质数，则p就是i的最小质因子。
此时若继续用更大的质数p'去划i×p'，由于i的最小质因子是p（且p < p'），所以i×p'的最小质因子仍然是p而不是p'——这个合数本该由p来划，现在被p'划了一次，将来还会被p再划一次，重复了。所以必须停。

自检恒等式：合数被标记的次数 == 合数的个数。n = 10⁶上两边都是 921,500，完全相等。

丑数：筛法的对偶形态

LC.263 判断丑数：反复除以2、3、5，看最后是否得到1。

LC.264 求第n个丑数用三指针正向生成：

ugly[0] = 1
i2, i3, i5分别指向"下一个要乘2/3/5的丑数下标"
每轮取min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)作为新丑数

⚠️ 去重必须用三个并列的if，不能用elif。
因为6 = 2×3 = 3×2，若用elif，只会推进其中一个指针，6就会被加入两次。

---

🖼️ 图解算法（手把手走一遍）

n = 20时埃氏筛的逐轮过程

轮次	当前质数 i	划掉的序列（从i²开始）	本轮新划掉
1	2	4, 6, 8, 10, 12, 14, 16, 18	8 个
2	3	9, 15	2 个（6/12/18已划）
3	5	—	0 个（25 > 20）
结果	—	—	质数：2,3,5,7,11,13,17,19共 8 个

注意第2轮只划了9和15——12和18在第1轮就被2划掉了。这就是“从i*i开始”省下的工作量。

n = 20 时欧拉筛的划掉次数对照

i	primes列表	本轮划掉	是否在i % p == 0处 break
2	[2]	4	在p=2处
3	[2,3]	6, 9	在p=3处
4	[2,3]	8	在p=2处（不划12）
5	[2,3,5]	10, 15	在p=5处
6	[2,3,5]	12	在p=2处（不划18、30）
7	[2,3,5,7]	14	在p=7处

关键看i=4：划掉8之后遇到p=2，因为4 % 2 == 0立即break，不划4×3 = 12。
为什么？12的最小质因子是2，它应该在i=6, p=2时被划掉（表中确实如此）。

验证恒等式（n = 20）：合数有4,6,8,9,10,12,14,15,16,18共 10个；欧拉筛的划掉次数也是 10次——完全相等，无重复 ✓

LC.264 三指针生成丑数（前10个）

轮次	×2候选	×3候选	×5候选	取最小	推进的指针
1	2	3	5	2	i2
2	4	3	5	3	i3
3	4	6	5	4	i2
4	6	6	5	5	i5
5	6	6	10	6	i2和i3（并列if！）
10	—	—	—	12	—

第 5 轮是关键：×2和×3都给出6，必须两个指针都推进。

---

💻 代码实现（Python + Java）

Python版

class Solution:
    # ---------- LC.204 埃氏筛（推荐：简洁且实测快）----------
    def countPrimes(self, n: int) -> int:
        if n < 2:
            return 0
        is_prime = [True] * n
        is_prime[0] = is_prime[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if is_prime[i]:
                # 从i*i开始划：更小的倍数已被之前的质数划掉
                for j in range(i * i, n, i):
                    is_prime[j] = False
        return sum(is_prime)

    # ---------- LC.204 欧拉筛（线性，理论最优）----------
    def countPrimesEuler(self, n: int) -> int:
        if n < 2:
            return 0
        is_comp = [False] * n
        primes = []
        for i in range(2, n):
            if not is_comp[i]:
                primes.append(i)
            for p in primes:
                if i * p >= n:
                    break
                is_comp[i * p] = True
                if i % p == 0:      # p 已是i的最小质因子
                    break
        return len(primes)

    # ---------- LC.263 丑数 ----------
    def isUgly(self, n: int) -> bool:
        if n <= 0:
            return False
        for p in (2, 3, 5):
            while n % p == 0:
                n //= p
        return n == 1              # 1是丑数

    # ---------- LC.264 丑数II ----------
    def nthUglyNumber(self, n: int) -> int:
        ugly = [1]
        i2 = i3 = i5 = 0
        for _ in range(n - 1):
            a, b, c = ugly[i2] * 2, ugly[i3] * 3, ugly[i5] * 5
            nxt = min(a, b, c)
            ugly.append(nxt)
            # 必须用三个并列if：6 = 2*3 = 3*2
            if nxt == a: i2 += 1
            if nxt == b: i3 += 1
            if nxt == c: i5 += 1
        return ugly[-1]

Java版

class Solution {
    public int countPrimes(int n) {
        if (n < 2) return 0;
        boolean[] isPrime = new boolean[n];
        java.util.Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; (long) i * i < n; i++) {   // i*i可能溢出
            if (isPrime[i]) {
                for (long j = (long) i * i; j < n; j += i) {
                    isPrime[(int) j] = false;
                }
            }
        }
        int cnt = 0;
        for (boolean b : isPrime) if (b) cnt++;
        return cnt;
    }

    public boolean isUgly(int n) {
        if (n <= 0) return false;
        for (int p : new int[]{2, 3, 5}) {
            while (n % p == 0) n /= p;
        }
        return n == 1;
    }

    public int nthUglyNumber(int n) {
        int[] ugly = new int[n];
        ugly[0] = 1;
        int i2 = 0, i3 = 0, i5 = 0;
        for (int k = 1; k < n; k++) {
            int a = ugly[i2] * 2, b = ugly[i3] * 3, c = ugly[i5] * 5;
            int nxt = Math.min(a, Math.min(b, c));
            ugly[k] = nxt;
            if (nxt == a) i2++;
            if (nxt == b) i3++;
            if (nxt == c) i5++;
        }
        return ugly[n - 1];
    }
}

⚠️ 防坑提醒（必看）：

• 埃氏筛从i*i 开始，不是2*i；Java里i*i可能超int，比较时用(long) i * i。
• 欧拉筛的break必须在标记之后：先标is_comp[i*p] = True，再判断i % p == 0。写反会导致i*p没被标记。
• LC.264去重必须用并列if，用elif时6会被加入两次。

---

⏱️ 复杂度分析（面试必问）

方法	时间复杂度	空间	关键
试除法	O(n√n)	O(1)	只试除到 √x
埃氏筛	O(nloglogn)	O(n)	从i*i开始划
欧拉筛	O(n)	O(n)	每个合数只被最小质因子划一次

实测：理论最优的欧拉筛，真的最快吗？

CPython四种实现（结果全部一致）：

n = 10⁵（质数9,592个）

实现	耗时	相对
埃氏筛（切片赋值版）	0.001s	1×
埃氏筛（朴素循环版）	0.004s	4×
欧拉筛	0.012s	13.4×
试除法	0.181s	181×

n = 10⁶（质数78,498个）

实现	耗时	相对
埃氏筛（切片赋值版）	0.019s	1×
埃氏筛（朴素循环版）	0.091s	4.8×
欧拉筛	0.143s	7.6×
试除法	5.994s	315×

结论很反直觉：理论上O(n)的欧拉筛，实测比O(nloglogn) 的埃氏筛慢7.6倍。

原因是实现层面的，不是算法层面的：

• 埃氏筛的内层可以用切片赋值 is_prime[i*i:n:i] = [False] * k，这是 C层的批量写入，几乎不经过Python解释器循环
• 欧拉筛的内层必须逐个判断i % p == 0并可能break，这是一个纯Python层的循环，每次迭代都有完整的解释开销

换句话说：埃氏筛用更少的“Python指令”完成了更多的工作。

那还要学欧拉筛吗？要，三个理由：

1. 换语言会反转。Java的boolean[]是连续内存、写入极快，而欧拉筛的分支判断在JIT下被摊薄——在C/C++/Java里两者差距会显著缩小，欧拉筛常能扳回来。
2. 欧拉筛顺带得到质数列表，且每个合数的最小质因子关系可用。质因数分解、欧拉函数（φ）、莫比乌斯函数等进阶算法都依赖线性筛的结构。
3. 它证明了一件更重要的事：break那一行背后是“最小质因子唯一”这个数论事实，理解它比记住代码有价值。

本周第二次“理论更优、实测更慢”（第一次是Brian Kernighan）。两次遇到同一件事，就该提炼成规则了。

---

🚀 举一反三：6 道高频变体题

题号	题目	与本题的关系
LC.263	丑数	质因子判定的简化版
LC.264	丑数II	三指针/堆，筛法的对偶形态
LC.1175	质数排列	筛 + 阶乘 + 快速幂
LC.952	按公因数计算最大组件大小	筛 + 并查集
LC.279	完全平方数	也可以用筛预处理平方数
LC.204	计数质数	本题

---

💬 面试追问模拟（提前准备，惊艳全场）

Q1：欧拉筛的那行break为什么正确？

当p整除i时，p就是i的最小质因子。
此时对任何p' > p，合数i×p'的最小质因子仍是p。
若现在用p'去划，将来还会被p再划一次——重复了。所以必须在第一个整除的p处停止。

Q2：怎么验证“每个合数只被划一次”？

用恒等式：合数被标记的次数 == 合数的个数。n = 10⁶时被标记921,500次，合数也恰好921,500 个（10⁶ - 78,498 - 2 = 921,500）✓。这个恒等式可以直接写进测试脚本当断言。

Q3：埃氏筛为什么从i*i开始？

2*i, 3*i, ..., (i-1)*i这些数，都含有一个小于i的质因子，在之前的轮次里已经被划掉了。从i*i开始可以避免重复劳动。

Q4：丑数II的三指针为什么不能用elif？

因为6 = 2×3 = 3×2，它可以由两个不同的指针产生。
用elif只会推进其中一个，下一轮另一个指针又给出6，导致6被加入两次。
三个并列的if才能保证每个候选值只推进一次。

---

🧩 实战小技巧（刷题党必备）

• 口诀：埃氏筛从i²划，欧拉筛遇整除即停；丑数三指针，并列if防重复。
• 模板：埃氏筛 = [True]*n + range(i*i, n, i)；欧拉筛 = primes + if i % p == 0: break。
• 防坑：i*i溢出用long；LC.264用并列if；欧拉筛先标记再break。

---

📈 实际应用场景（不止是刷题）

• 密码学：RSA需要生成大质数，筛法是基础工具
• 哈希与随机数：质数大小的哈希表容量能减少冲突
• 数论预处理：欧拉函数 φ、莫比乌斯函数μ都基于线性筛
• 批量判定：需要反复判断“某个数是否为质数”时，一次筛出表比逐个试除划算得多

---

🎁 今日思考题

实测显示Python里埃氏筛（切片版）比欧拉筛快7.6倍。
如果面试官问“既然欧拉筛是O(n)，为什么你不用它？”，你会怎么回答？
另外：你能想到让欧拉筛在Python里也跑得快一些的办法吗？