【leetcode系列】【算法】【简单】计数质数(埃拉托斯特尼筛法sieve of Eratosthenes)
程序员文章站
2022-06-08 13:23:04
...
题目:
题目链接: https://leetcode-cn.com/problems/count-primes/
解题思路:
方法一:遍历(时间O())
判断n是否为质数,只需要从2开始,遍历到,如果没有可以整除的,则n是质数;反之,如果找到可以整除的,n就为合数
方法二:埃拉托斯特尼筛法(时间O(N * loglogN))
借用wiki上的动态图:
从2开始遍历,2是一个质数,2的所有倍数均不是质数,将此部分数都排除掉,继续遍历3,再次排除掉所有3的倍数,依次类推
最后剩余的数字,就是要找的质数
代码实现:
方法二:
class Solution:
def countPrimes(self, n: int) -> int:
rec = [1] * (n)
num = 0
for i in range(2, n):
if 1 == rec[i]:
# 从i * i开始, 遍历到n结束
# 因为比i * i小的数字,在本次遍历之前,就已经排除掉了
# 而且当i * i > n的时候,就不需要进行里面的判断了
for j in range(i * i, n, i):
rec[j] = 0
# 因为从2开始的,所以遍历到后面时,比如10,已经被2或者5排除掉了
# 所以如果遍历到当前数字是质数,那就是真的质数
num += 1
return num