LeetCode Algorithm 204. 计数质数

204. 计数质数

Ideas

质数的题目相对来说是个很经典的内容，虽然枚举也可以解决，但是复杂度很高，所以决定用埃氏筛来实现。

埃氏筛的基本思想是：从2开始，将每个质数的倍数都标记成合数。

Code Python

class Solution: def countPrimes(self, n: int) -> int: ans, isPrimer = 0, [True] * n # isPrimer 用于标记是否为质数 for i in range(2, n): if isPrimer[i]: ans += 1 for k in range(2, n): if i * k < n: isPrimer[i * k] = False # 将质数 i 的倍数都标记为合数 else: break return ans