埃式筛/厄拉多塞筛法/Sieve_of_Eratosthenes/计数质数

今天的每日一题是计数质数。
要求统计所有小于非负整数 n 的质数的数量。

• 为了解这题，学到了一个古老的魔法，快速寻找质数。

搜了下百度，keywords = “prime” "python"的时候，出来的大部分都是暴力法，容易超时啊啊啊。原以为质数这种常用的东西会有包，结果一个个的全暴力，太没有美感了！（其实我一开始也写的brute force…

Let’s start the advanture!

In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.

思想非常简单，我们从2开始遍历[1,2,…,n]的数组，遇到质数的时候（比如2），就把数组类所有它的倍数都标记成合数（对应2的话，一下子就把4，6，8，…所有的偶数都筛掉了)。

什么时候终止呢？当我遍历的元素的平方大于n的时候就可以停了。

下面这张图就很清晰了。实际上只筛了2，3，5，7的倍数，到11的时候就终止了，剩下的没被筛出去的数字都是质数了。

理论依据是算术基本定理：

任何一个大于1的自然数 N，如果N不为质数，那么N可以唯一分解成有限个质数的乘积。

如果在根号n以内都找不到因子，那么这些剩下的数字，只可能是老光棍质数啦。

附上代码：

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2: return 0
        isPrime = [1] * n
        isPrime[0], isPrime[1] = 0, 0
        for i in range(2,int(n**0.5)+1):
            if isPrime[i] == 0:
                continue
            for x in range(2,(n-1)//i+1):
                isPrime[i*x] = 0
        return sum(isPrime)