寫在開頭

這題也是一個#Easy

進入正題

題目如下：

Count the number of prime numbers less than a non-negative number, n.
Example:
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

我想到的方法是，找出輸入數字以下的所有質數(參考1的做法)，但質數需要一一判斷，做法可能會花很多時間：

def countPrimes(self, n: int) -> int:
    count = 0
    for num in range(n):
        if num > 1:
           for i in range(2,num):
               if (num % i) == 0:
                   break
           else:
               count = count + 1
    return count

這個方法雖然測試有跑過，但submit後的結果說超過時間：


得換個方法才行，所以我又找到了參考2，取得100以內的質數的方法有兩種，另外一個是用filler()函數來過濾掉不符合條件的數字，使用的方法可以看參考3，呼叫的時候會需要設定2個參數輸入，分別是過濾用的function和序列區間。修改後程式碼如下：

def countPrimes(self, n: int) -> int:
    def func_get_prime(num):
        return filter(lambda x: not [x%i for i in range(2, int(math.sqrt(x))+1) if x%i ==0], range(2,num))

    return len(list(func_get_prime(n)))

Submit後還是超過時間：

想不到其他的方法來解這個題目，只好去搜尋、研究別人的做法。查的時候找到了參考4介紹的一個方式，叫厄拉多篩法，是找質數的一種方法，會把找的那個質數的倍數都給先排除，因此需要搜尋、確認的數字就會變少。所以他的做法是這樣：

def countPrimes(self, n: int) -> int:
    if n < 3:
        return 0
    primes = [True] * n
    primes[0] = primes[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if primes[i]:
            primes[i * i: n: i] = [False] * len(primes[i * i: n: i])
    return sum(primes)

Submit後速度就及格了，最後結果如下：

參考資料

參考1Python 质数判断
參考2Python - 获取 100 以内的质数
參考3Python3 filter() 函数
參考4Python 刷题日记：LeetCode 204: Count Primes