leetcode上的204题，寻找小于非负数n的质数个数。
这个题，用暴力法肯定会超时，优化一点的暴力法还是会超时。一般来说，寻找质数主要是两种方法，埃式筛和欧拉筛。
埃式筛即埃拉托斯特尼筛法，也叫厄拉多塞筛法。这是由古希腊数学家埃拉托斯特提出来的，该算法是说要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。
python实现：
代码语言：javascript复制class Solution:
def countPrimes(self, n: int) -> int:
if n <= 2:
return 0
res = [1 for i in range(n)]
res[0], res[1] = 0, 0
p = 2
while p < int(n ** 0.5) 1:
if res[p]: # 如果是质数，将所有质数的倍数都改为0
for i in range(p ** 2, n, p): 在p**2之前的已经计算过了
res[i] = 0
p = 1
return sum(res)
