难度: Medium
给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
示例 1：
输入：n = 10 输出：4 解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2：
输入：n = 0 输出：0
示例 3：
输入：n = 1 输出：0
提示：
0 <= n <= 5 * 106
Submission
运行时间: 54 ms
内存: 16.2 MB
class Solution:
def countPrimes(self, n: int) -> int:
isNumPrimes = [True] * n # 将所有数，展开所有数 标记质数真
count = 0 # 质数计数器 因为1不是质数 所以 0
# 遍历2，n 数，判断是否是质数，从2开始对应-质数3 [1,2,3] 1不算质数
for i in range(2, n):
if isNumPrimes[i]:
count += 1
# 使用埃拉托斯特尼 筛选法进行过滤 将合数去除
for j in range(i*i, n, i): #遍历 i*i 2倍i值 开始，结束n, 步数i (倍数递增)
isNumPrimes[j] = False # 把合数置为 False
return count
Explain
此题解采用了经典的埃拉托斯特尼筛法（Sieve of Eratosthenes）来寻找所有小于非负整数 n 的质数。首先，算法创建一个布尔数组 isNumPrimes 来跟踪每个数是否为质数，初始化时假设所有数都是质数。接着，通过遍历2到n的每个数，如果发现一个数i是质数（isNumPrimes[i]为True），则将i的所有倍数设置为非质数（False），从而筛选掉非质数。这里需要注意的是，筛选从i*i开始，因为小于i*i的倍数在之前已经被筛选过了。最终，数组中为True的位置表示该位置的索引是质数，通过计数这些位置得到小于n的所有质数的数量。
时间复杂度: O(n log log n)
空间复杂度: O(n)
class Solution:
def countPrimes(self, n: int) -> int:
if n <= 2:
return 0 # 小于2的n没有质数
isNumPrimes = [True] * n # 初始化布尔数组，假设所有数都是质数
count = 0 # 质数计数器
for i in range(2, n): # 从2开始到n-1
if isNumPrimes[i]: # 如果i是质数
count += 1 # 计数增加
for j in range(i * i, n, i): # 从i*i开始到n，步长为i
isNumPrimes[j] = False # 将i的倍数设置为非质数
return count # 返回质数计数
Explore
在筛选算法中，当我们确定一个数i是质数时，我们需要筛除所有i的倍数，因为它们不是质数。如果我们从2*i开始筛选（也就是i+i），我们会重复筛除那些已经在处理更小的质数时被筛除的数。例如，当i=5时，10已经在处理i=2时被筛除。从i*i开始筛选可以避免这种重复，因为i的所有较小倍数（例如k*i，其中k<i）已经在处理小于i的质数k时被考虑过了。这样不仅避免了重复工作，还提高了效率。
在执行埃拉托斯特尼筛法时，实际上只需要考虑到n的平方根为止。因为如果n不是质数，并且它有一个因子大于其平方根，则其对应的另一个因子必定小于平方根。因此，如果在到达n的平方根时还未将数筛出，则之后的数无需继续检查，它们会自然保留为质数，或者在处理小于平方根的质数时已经被筛除。
将布尔数组isNumPrimes的所有值初始化为True意味着我们在开始筛选之前假定所有数都是质数。这种初始化策略是必要的，因为它定义了筛选的起始状态。这种做法导致的空间复杂度是O(n)，因为我们需要一个与输入大小n相对应的布尔数组来存储每个数的状态。虽然这增加了算法的空间需求，但这是实现埃拉托斯特尼筛法所必须的，以确保能有效地筛选出非质数。