iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 30
0

寫在開頭

這題也是一個#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後的結果說超過時間:
https://ithelp.ithome.com.tw/upload/images/20190930/20113393NKxUEDls6f.png
https://ithelp.ithome.com.tw/upload/images/20190930/20113393UpF1k8rVC7.png
得換個方法才行,所以我又找到了參考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後還是超過時間:
https://ithelp.ithome.com.tw/upload/images/20190930/201133938AvD8so7hX.png
想不到其他的方法來解這個題目,只好去搜尋、研究別人的做法。查的時候找到了參考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後速度就及格了,最後結果如下:
https://ithelp.ithome.com.tw/upload/images/20191001/20113393Ifk2DpSrSR.png

參考資料

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


上一篇
#69 Sqrt(x)
下一篇
Day31 一點點鐵人賽的小心得
系列文
Leetcode新手挑戰30天31

尚未有邦友留言

立即登入留言