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

题目：

题目链接： 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