**描述**：给定 一个非负整数 `n`。

**要求**：统计小于 `n` 的质数数量。

**示例**：

输入 n = 10

输出 4

解释 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

对于小于 `n` 的每一个数 `x`，我们可以枚举区间 `[2, x - 1]` 上的数是否是 `x` 的因数，即是否存在能被 `x` 整数的数。如果存在，则该数 `x` 不是质数。如果不存在，则该数 `x` 是质数。

这样我们就可以通过枚举 `[2, n - 1]` 上的所有数 `x`，并判断 `x` 是否为质数。

在遍历枚举的同时，我们维护一个用于统计小于 `n` 的质数数量的变量 `cnt`。如果符合要求，则将计数 `cnt` 加 `1`。最终返回该数目作为答案。

考虑到如果 `i` 是 `x` 的因数，则 $\frac{x}{i}$ 也必然是 `x` 的因数，则我们只需要检验这两个因数中的较小数即可。而较小数一定会落在 $[2, \sqrt x]$ 上。因此我们在检验 `x` 是否为质数时，只需要枚举 $[2, \sqrt x]$ 中的所有数即可。

利用枚举算法单次检查单个数的时间复杂度为 $O(\sqrt{n})$，检查 `n` 个数的整体时间复杂度为 $O(n \sqrt{n})$。

class Solution:

def isPrime(self, x):

for i in range(2, int(pow(x, 0.5)) + 1):

if x % i == 0:

return False

return True

def countPrimes(self, n: int) -> int:

cnt = 0

for x in range(2, n):

if self.isPrime(x):

cnt += 1

return cnt

可以用「埃氏筛」进行求解。这种方法是由古希腊数学家埃拉托斯尼斯提出的，具体步骤如下：

- 使用长度为 `n` 的数组 `is_prime` 来判断一个数是否是质数。如果 `is_prime[i] == True` ，则表示 `i` 是质数，如果 `is_prime[i] == False`，则表示 `i` 不是质数。并使用变量 `count` 标记质数个数。

- 然后从 `[2, n - 1]` 的第一个质数（即数字 `2`） 开始，令 `count` 加 `1`，并将该质数在 `[2, n - 1]` 范围内所有倍数（即 `4`、`6`、`8`、...）都标记为非质数。

- 然后根据数组 `is_prime` 中的信息，找到下一个没有标记为非质数的质数（即数字 `3`），令 `count` 加 `1`，然后将该质数在 `2, n - 1]` 范围内的所有倍数（即 `6`、`9`、`12`、…）都标记为非质数。

- 以此类推，直到所有小于或等于 `n - 1` 的质数和质数的倍数都标记完毕时，输出 `count`。

优化：对于一个质数 `x`，我们可以直接从 `x * x` 开始标记，这是因为 `2 * x`、`3 * x`、… 这些数已经在 `x` 之前就被其他数的倍数标记过了，例如 `2` 的所有倍数、`3` 的所有倍数等等。

for j in range(i * i, n, i):