Algorithm

204. 计数质数

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

示例:

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

解法一，暴力法：

class Solution:
    def countPrimes(self, n: int) -> int:
        count = 0
        
        for i in range(n):
            if self.isPrime(i):
                count += 1
                
        return count
    
    def isPrime(self, n) -> bool:
        if n < 2:
            return False
        
        if n == 2:
            return True
        
        i = 2
        
        while i <= int(n ** 0.5):
            
            if n % i == 0:
                return False
            
            i += 1
            
        return True

其中这里利用了一个数学规律：

假设一个数 N 他有两个约数 a、b，当 a = b 时，那么它是一个合数，也就是 a^2 = N。

如果他的这两个约数都大于 根号 N ，也就是 a > 根号 N，那么一定有 a ^ > N。

所以若 N 不是质数，那么必定存在一个约数小于等于根号 N（1 除外）。

虽然利用了数学规律，但是暴力法超时了 🤪。

解法二，埃拉托色尼筛网法：