埃拉托斯特尼筛法

基本概念

核心定义：一种用于找出小于等于给定整数N的所有质数的古老算法。
核心思想：“排除法”。与其逐个判断每个数是不是质数，不如反过来：从 2 开始，把每一个质数的倍数全部标记为“合数（非质数）”。剩下的未被标记的数就是质数。
数据结构：通常使用一个布尔数组（Boolean Array）来维护状态。数组索引代表数字本身，值代表该数字是否为质数（True/False）。

费曼理解 (Feynman Technique)

用最简单的语言解释给“小白”听：

想象操场上有编号 2 到 100 的 100 个学生，他们都默认站着（代表是质数）。

第一步：老师喊 2（最小的质数）。2 说：“凡是能被 2 整除的同学（4, 6, 8…），请坐下（排除）。”

第二步：老师喊下一个还站着的同学 3。3 说：“凡是能被 3 整除的同学（6, 9, 12…），请坐下。”

重复：老师继续找下一个还站着的同学（5, 7…），直到检查完 100100 （即 10）为止。

最后：操场上还站着的同学，他们的编号就是质数。

3. 内部实现：核心代码逻辑

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2:
            return 0
        
        # 1. 初始化：创建一个长度为 n 的布尔数组
        # 默认所有数都是质数 (True)，0 和 1 特判为 False
        is_prime = [True] * n
        is_prime[0] = is_prime[1] = False

        # 2. 筛选过程：从 2 遍历到 sqrt(n)
        # (因为大于 sqrt(n) 的合数，其因子必然小于 sqrt(n)，已经被筛过了)
        for i in range(2, int(n ** 0.5) + 1):
            if is_prime[i]: # 如果 i 是质数
                # 3. 核心操作：将 i 的所有倍数标记为非质数
                # 优化：从 i*i 开始标记（因为 i*2, i*3... 在之前已经被标记过了）
                for j in range(i * i, n, i):
                    is_prime[j] = False
        
        # 4. 统计结果：计算小于 n 的质数个数
        # (也可以返回 [i for i, prime in enumerate(is_prime) if prime] 来获取具体数值)
        return sum(is_prime)

代码逻辑拆解：

预处理：创建数组，排除 0 和 1。
外层循环：遍历 $[2,n]$ 。为什么是 n ？因为如果n有一个大于 n 的因数，必然有一个小于n的对应因数，所以只需筛到n。
内层循环：关键优化点。对于质数i，我们从i×i开始标记，步长为i。这是因为 i×2,i×3…i×2,i×3… 在之前已经被 2, 3 筛过了，从 $i^2$ 开始是效率最高的。

复杂度分析

指标	复杂度	说明
时间复杂度	O(N⁡log⁡N)	这是一个非常接近线性的时间复杂度。虽然有两层循环，但由于内层循环只在 i 是质数时才执行，且步长递增，其数学期望极低。
空间复杂度	O(N)	需要一个长度为 N 的布尔数组来存储每个数的状态。