前情提要

求质数最简单的方法是暴力破解：

def isPrime(n):
    if n < 2: # 如果n比2小的话，你判断它干嘛
      return False
    elif n == 2: # 2是个质数
      return True

    res = True
    
    for i in range(3 , n):
        for j in range(2, n):
          if i % j == 0:
              res = False
              break

    return res

但这样做的效率会很低。有没有办法提高效率呢？

筛选法的核心就一句话：质数的整数倍不是质数。例如，2是质数，但4、6、8等都不是质数，因为它们分别是2的2倍、3倍、4倍等等。同理，3是质数，6、9、12、15等也都不是质数了。

那么如何实现呢？

题目：Leetcode-204.计数质数

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2:  # 原题目要求是小于n范围内有多少质数？如果小于2的话，那么就没有。
            return 0
        
        isPrime = [True for i in range(n)] # 打表。打一个长度为n的表，表示从0到n-1（包括n-1在内）有哪些是质数。一上来默认全是质数
        isPrime[0] = isPrime[1] = False # 由于0和1什么都不算，所以上来就给它们置为False

        for i in range(2, n): # 从2开始计算
            if isPrime[i] is True: # 由于2肯定是质数，所以放心的算吧。这个条件的意思是如果i是质数的话
                for j in range(2, (n - 1) // i + 1):  # j在2倍到小于n的情况下i的最大倍数的范围
                    isPrime[i * j] = False # i的倍数全置于False
        
        res = 0 # 返回的结果
        for tf in isPrime: # 那么对照筛选出来的正负表
            if tf is True: # 每遇到一个True
                res += 1 # 返回的结果数加1
        
        return res