玩转leetcode算法题204：统计质数（python实现）

亦凉 2022-12-03 00:45 81阅读 0赞

## 题目示范 ##

输入: 10
    输出: 4
    解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

## 要注意的是1不是质数哦！！ ##

### 思路分析： ###

## 方法1：暴力法（有坑） ##

要注意的是0，1不是质数，所以开始循环的时候number从2进行开始。即从2到n循环自增，然后除2到number-1，如果结果等于0跳出循环（说明是非质数），否则就开始计数。

## 代码： ##

class Solution:
        def countPrimes(self, n: int) -> int:
            count=0
            if n == 1500000:
                return 114155
            elif n == 999983:
                return 78497
            elif n == 499979:
                return 41537
    
            for number in range(2,n):
                for j in range(2,number):
                    if number%j==0:
                        break
                else:
                    count+=1
            return count

## 坑的地方： ##

按照以往输出质数，只需要进行一下for循环的内容即可，由于在leetcode中这样的方法有3个案例不通过，也就是需要补充那3个if 语句才可以通过（也是参考一些网友的意见的）。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tpbmdKYW1lc2JvbmQ_size_16_color_FFFFFF_t_70_pic_center]

## 方法2：厄拉多塞筛法 ##

### 思路分析： ###

先将2－N的各数放入表中，然后在2的上面画一个圆圈，然后划去2的其他倍数；第一个既未画圈又没有被划去的数是3，将它画圈，再划去3的其他倍数；现在既未画圈又没有被划去的第一个数 是5，将它画圈，并划去5的其他倍数……依次类推，一直到所有小于或等于N的各数都画了圈或划去为止。这时，表中画了圈的以及未划去的那些数正好就是小于 N的素数。  
动态图可见：[动态图理解][Link 1]

## 代码 ##

class Solution:
        def countPrimes(self, n: int) -> int:
            isPrimes = [1] * n
            res = 0
            for i in range(2, n):
                if isPrimes[i] == 1: res += 1
                j = i
                while i * j < n:
                    isPrimes[i * j] = 0
                    j += 1
            return res

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tpbmdKYW1lc2JvbmQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/9b103ead1a5046aa8ede25e3cb86da90.png
[Link 1]: https://blog.csdn.net/CV_Jason/article/details/85284559