題目：

統(tǒng)計所有小于非負整數(shù) n 的質(zhì)數(shù)的數(shù)量。

方法一：
暴力法

class Solution:def countPrimes(self, n: int) -> int:count = 0if n > 1:for i in range(2, n):flag = Truefor j in range(2, i):if i % j == 0:flag = Falsebreakif flag:count += 1return count

方法雖簡單，但是時間超時了，無法通過測試

方法二：
厄拉多塞篩法，力扣上看到大神分享的方法：
比如說求20以內(nèi)質(zhì)數(shù)的個數(shù),首先0,1不是質(zhì)數(shù).2是第一個質(zhì)數(shù),然后把20以內(nèi)所有2的倍數(shù)劃去.2后面緊跟的數(shù)即為下一個質(zhì)數(shù)3,然后把3所有的倍數(shù)劃去.3后面緊跟的數(shù)即為下一個質(zhì)數(shù)5,再把5所有的倍數(shù)劃去.以此類推.

class Solution: def countPrimes(self, n: int) -> int:if n < 3:return 0else:output = [1] * n # 產(chǎn)生一個元素全部為1的列表output[0], output[1] = 0, 0 # 0,1不是質(zhì)數(shù)，直接賦值為0for i in range(2, int(n**0.5)+1): # 從2開始，output[2]==1表示第一個質(zhì)數(shù)是2，然后將2的倍數(shù)對應(yīng)的索引全部賦值為0，此時下一個數(shù)output[3]==1,也是表示質(zhì)數(shù)，同樣劃去3的倍數(shù)，以此類推if output[i] == 1:output[i*i:n:i] = [0] * len(output[i*i:n:i])#最后output中的數(shù)字表示該位置上的數(shù)為質(zhì)數(shù)，然后求和即可return sum(output)

總結(jié)

以上是生活随笔為你收集整理的python力扣刷题记录——204. 计数质数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。