204. 计数质数
给定整数
n ，返回 所有小于非负整数 n 的质数的数量 。示例 1：
输入：n = 10 输出：4 解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2：
输入：n = 0 输出：0
示例 3：
输入：n = 1 输出：0
提示：
0 <= n <= 5 * 106
通过次数189,363提交次数503,043
法 1 埃氏筛法
思路
参考 质数 or 素数
题解
class Solution: def countPrimes(self, n: int) -> int: primes = [] st = [False for _ in range(n)] for i in range(2, n): if st[i] is False: primes.append(i) # 筛掉当前质数的所有倍数 # 从 2 倍 开始筛 j = i + i while j < n: st[j] = True j += i return len(primes)
线性筛法
思路
参见 质数 or 素数
题解
class Solution: def countPrimes(self, n: int) -> int: primes = [] st = [False for _ in range(n)] for i in range(2, n): if st[i] is False: primes.append(i) for p in primes: if i * p >= n: break st[p * i] = True if i % p == 0: break return len(primes)