找质数的方式
在很多编程题中，可能需要找出小于N的质数，一般的枚举算法是比较费时的(比如遍历小于的所有数，判读其是否是n的因子)，这里介绍一种更为高效的算法：埃氏筛
步骤如下：
- 使用长度为 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中的信息，找到下一个没有标记为非质数的质数 - 以此类推，直到所有小于或等于 n−1 的质数和质数的倍数都标记完毕时，输出
count - 优化：对于一个质数 y，我们可以直接从 y×y 开始标记，这是因为 2×y、3×y、… 这些数已经在 y 之前就被其他数的倍数标记过了，例如 2 的所有倍数、3 的所有倍数等等。
class Solution: def countPrimes(self, n: int) -> int: is_prime = [True] * n count = 0 for i in range(2, n): if is_prime[i]: count += 1 for j in range(i * i, n, i): is_prime[j] = False return count