[204] 计数质数

链接：计数质数

1.判断一个数是否为素数的方法

1. 从判断是否有的因数，如果不能找到因数，则是素数。

def is_prime(n):
    for e in range(2, n):
        if n % e == 0:
            return False
    else:
        return True

2. 从判断是否有的因数，如果不能找到因数，则是素数。

def is_prime(n):
    for e in range(2, int(sqrt(n))+1):
        if n % e == 0:
            return False
    else:
        return True

2.标记小于数的全部素数

对于这个问题，可以对中每个元素使用的算法进行判断，整体的时间复杂度为，在本题的case中会超时。

这个问题可以使用埃式筛算法来快速找到小于的所有素数，具体流程如下

1. 创建一个长度为的bool标记数组，除了0，1两个位置外，其余元素初始化为True。
2. 当我门找到一个素数时，对这个素数的所有倍数，都置为False，即这些数都是合数。这里有个优化点，即当 比较大时（比如），对应的，会在之前的遍历中被置为False，因此只需要对进行置False操作。
3. 的范围，因为对每个素数，我们是从 开始置False，当时，便没有数可以置False，因此遍历时的范围是 。

class Solution:
    def countPrimes(self, n: int) -> int:
        if n < 2:
            return 0

        nums = [True] * n
        nums[0], nums[1] = False, False
        
        for i in range(2, int(n**0.5)+1):
            if nums[i]:
                for j in range(i*i, n, i):
                    nums[j] = False
        
        return sum(nums)