204. 计数质数 (Count Primes)

🎯 问题描述（来源于LeetCode）

描述：给定整数 n，返回所有小于 n 的非负质数的数量。

说明：

质数：在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
注意是 小于 n，不包含 n 本身。

示例：

示例 1：

1
2
3

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个，分别为 2, 3, 5, 7。

示例 2：

1
2
3

输入：n = 0
输出：0
解释：没有小于 0 的数。

💻 解题思路

思路1：枚举优化（试除法）

这是一个典型的枚举算法应用。我们需要遍历从 2 到 n-1 的每一个数字，并判断其是否为质数。

核心优化点（剪枝）：
单纯枚举 1 到 n 判断是否整除的时间复杂度是 $O(N)$ 。利用数学性质可以将其优化至 $O(\sqrt{N})$ ：

平方根性质：如果一个数 $N$ 有因数，那么必然有一个因数小于或等于 $\sqrt{N}$ 。
实现：在判断质数函数 Iszhi 中，循环只需要从 2 遍历到 int(n ** 0.5) + 1 即可。

算法步骤：

特判：处理 n <= 2 的情况，直接返回 0（因为小于2的数中没有质数）。
外层循环：遍历 2 到 n-1 的每一个数 i。
内层判断：调用 Iszhi(i) 函数检查 i 是否为质数。
计数：如果是质数，计数器 count 加 1。

思路1：代码实现

class Solution:
    def Iszhi(self, n: int) -> bool:
        if n <= 1: 
            return False  # 0和1不是质数
        if n == 2: 
            return True   # 2是最小的质数
        
        # 核心优化：只需检查到 sqrt(n)
        # 使用 n ** 0.5 代替 math.sqrt(n)，int()会自动向下取整
        for i in range(2, int(n ** 0.5) + 1): 
            if n % i == 0:       
                return False     # 发现因数，不是质数
        return True              # 未发现因数，是质数

    def countPrimes(self, n: int) -> int:
        count = 0
        # 枚举从 2 到 n-1 的所有整数
        for i in range(2, n):
            if self.Iszhi(i):
                count += 1
        return count

思路1：📊 性能分析

复杂度验证

时间复杂度： $O(N \sqrt{N})$ $O (N N)$
- 外层循环需要遍历 $N$ 个数。
- 每个数进行质数判断需要 $O(\sqrt{N})$ 。
- 总体复杂度为 $N \times \sqrt{N}$ 。对于大数（如 $10^6$ ）可能会超时。
空间复杂度： $O(1)$ $O (1)$
- 只使用了常数级别的额外变量（count, i 等）。

💡 思考

1. 为什么循环上限是 `int(n ** 0.5) + 1`？

n ** 0.5：计算 $n$ 的平方根。
int()：将浮点数向下取整为整数。
+ 1：因为 range 函数是左闭右开区间（不包含结束值）。如果不加 1，当 $n$ 恰好是完全平方数（如 25）时，循环会在 4 结束，导致漏掉 5 这个因数，从而错误地判定 25 是质数。

2. 进阶思考：埃拉托斯特尼筛法

虽然上述代码逻辑正确，但在处理大数（如 $n = 5 \times 10^6$ ）时效率较低。

更优解法：可以使用埃拉托斯特尼筛法 (Sieve of Eratosthenes)。
原理：创建一个长度为 $n$ 的布尔数组，初始假设所有数都是质数。从 2 开始，将 2 的所有倍数（4, 6, 8…）标记为非质数，然后找下一个未被标记的数（3），再标记 3 的倍数。以此类推。
复杂度：时间复杂度可优化至 $O(N \log \log N)$ ，是解决此类问题的最优解之一。

3. 易错点总结

边界处理：n = 0 或 n = 1 时，循环 range(2, n) 不会执行，直接返回 0，这是正确的，但逻辑必须清晰。
数据类型：n ** 0.5 返回的是浮点数，必须用 int() 转换为整数才能用于 range。

思路2：埃拉托斯特尼筛法

思路2：代码实现

class Solution:    
    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]:
                for j in range(i**2,n,i):
                    is_prime[j]=False
        return sum(is_prime)