題目鏈接
難度：簡單 ??????類型： 數(shù)組

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

示例

輸入: 10
輸出: 4
解釋: 小于 10 的質(zhì)數(shù)一共有 4 個, 它們是 2, 3, 5, 7 。

解題思路

設(shè)置一個長度為n的數(shù)組 is_primes，用于記錄i是否為質(zhì)數(shù)，若是，is_primes[i]=True,反之為False
遍歷1到n的數(shù)，當(dāng)is_primes[i]是質(zhì)數(shù)是，將i的倍數(shù)位全部置False，例如：
當(dāng)i=2為質(zhì)數(shù)，就將4，6，8...全部修改為False
最終記錄is_primes中為True的個數(shù)即可

代碼實現(xiàn)

class Solution:
    def countPrimes(self, n: int) -> int:
        if n<2:
            return 0
        nums = list(range(n+1))
        is_primes = [True] * n
        counter = 0
        for i in range(2,n):
            if is_primes[i]:
                counter += 1
                is_primes[i*i:n:i] = [False] * len( is_primes[i * i: n: i])
        return counter

本文鏈接：http://www.itdecent.cn/p/c252d98448cc