LeetCode-Python-204. 计数质数
程序员文章站
2022-03-13 12:06:12
...
统计所有小于非负整数 n 的质数的数量。
示例:
输入: 10 输出: 4 解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
第一种思路:
暴力法,把0~n - 1每个数试一遍看是不是质数。
结果:稳定超时。
第二种思路:
厄拉多塞筛法,
核心思想就是:把已知质数的所有倍数标记为False。
时间复杂度是O(n log log n)。
class Solution(object):
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
record = [1] * n
for i in range(2, n):
if record[i] == 1:
for j in range(i * 2, n, i):
record[j] = 0
return sum(record) - 2 if n > 1 else 0
上一篇: 树中任意两个节点之间的距离