统计所有小于非负整数 n 的质数的数量。

示例 1：

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：0

提示：

• 0 <= n <= 5 * 106

Solution

参考：《算法小抄》5.1 、**@yiluoyion**

• 暴力解法，超时

# @lc code=start
class Solution:
    def countPrimes(self, n: int) -> int:
        cnt = 0
        def isPrime(num):
            for i in range(2, int(sqrt(num))+1):
                if num%i==0:
                    return False
            return True
        
        for i in range(2,n):
            if isPrime(i): cnt+=1
        return cnt
# @lc code=end

• 埃氏筛

埃氏筛的原理：从 2 开始，将每个质数的倍数都标记为合数。同样的，标记到$\sqrt{n}$停止。

假设一个数 i 为质数时，那么此时大于 i 且是 i 的倍数的数一定不是质数，例如 2i，3i..。那么我们将这些不是质数的数进行标记。

这里需要注意，标记应该从 i * i 开始，而不是 2 * i 开始。因为对于每个数 i 来说，枚举是从小到大的，此时前面数字的倍数都已经进行了标记。对于 i 而言，2 * i 也肯定会被在枚举数字 2 时进行标记，[2, i) 区间的数同理。

class Solution:
    def countPrimes(self, n: int) -> int:
        cnt = 0
        isPrime = [1]*n
        for i in range(2,n):
            if isPrime[i]:
                cnt += 1
                for j in range(i*i, n, i):
                    isPrime[j] = 0
        return cnt