leetcode 204 Count Primes(計算質數) python3 多種思路(動態素數表/埃氏篩法/)

NO IMAGE
class Solution:
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
# 思路一:  簡單的遍歷除以小於他的數,效率太低了!
# 思路二: 遍歷除以小於他一半的數,有率提升一倍
# 思路三:  動態建立素數表,這樣居然還不行?!效率還是低
# num = 0
# result = [2  ]
# for i in range(2, n):     
#     for j in range(len(result)):
#         if i % result[j] == 0 and i!=result[j]:
#             break
#         if j==len(result)-1:
#             result.append(i)
#             num  = 1
# return num
# 思路四: Sieve of Eratosthenes(埃拉托色尼篩法,簡稱埃氏篩法),參考維基百科:https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
# fasle 表示不是素數, true 代表素數. 所以總和是多少,最後就有多少個.
# 注意審題邊界條件,是小於n,不包括n
if n < 2:
return 0     # 注意 陣列越界的情況
primes = [True] * n
primes[0] = primes[1] = False
for i in range(2, int(n**0.5) 1):    # 在選擇除數時候的一個小技巧.大於一半的數是不可能做除數的. 事實證明, 能夠節省400ms的時間
if primes[i]:
primes[i * i: n: i] = [False] * len(primes[i * i: n: i])  # 非常簡潔的語句, 從小到大用埃氏篩法, 將每一個不是宿舍的數篩選掉.大大減少出發的數量.
return sum(primes)