欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【leetcode系列】【算法】【简单】计数质数(埃拉托斯特尼筛法sieve of Eratosthenes)

程序员文章站 2022-06-08 13:23:04
...

题目:

【leetcode系列】【算法】【简单】计数质数(埃拉托斯特尼筛法sieve of Eratosthenes)

题目链接: https://leetcode-cn.com/problems/count-primes/

 

解题思路:

方法一:遍历(时间O(【leetcode系列】【算法】【简单】计数质数(埃拉托斯特尼筛法sieve of Eratosthenes)))

判断n是否为质数,只需要从2开始,遍历到【leetcode系列】【算法】【简单】计数质数(埃拉托斯特尼筛法sieve of Eratosthenes),如果没有可以整除的,则n是质数;反之,如果找到可以整除的,n就为合数

 

方法二:埃拉托斯特尼筛法(时间O(N * loglogN))

借用wiki上的动态图:

【leetcode系列】【算法】【简单】计数质数(埃拉托斯特尼筛法sieve of Eratosthenes)

从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