Python 刷題日記:LeetCode 204: Count Primes

NO IMAGE
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

原題:
Description:

Count the number of prime numbers less than a non-negative number, n.

解題思路:

常規解法:

因為要求解小於n的素數個數,首先要解決如何判斷一個素數。那麼就是對於一個數x,只需對[2,這裡寫圖片描述]的數進行整除,若能整除則不是素數,不能整除則為素數。然後判斷小於n的各個數是否為素數,這樣做法的複雜度顯然為O(n^2),在LeetCode中肯定TLE。

def countPrimes(n):
import math
count=0
def judge_prime(w):
sqrt_w=int(math.sqrt(w))
for i in xrange(2,sqrt_w 1):
if x%i==0:
return 0
return 1
for x in xrange(2,n):
count=count judge_prime(x)
return count

解法二:厄拉多塞篩法

沒辦法了我就去Google了一下,於是知道了厄拉多塞篩法:

西元前250年,希臘數學家厄拉多塞(Eeatosthese)想到了一個非常美妙的質數篩法,減少了逐一檢查每個數的的步驟,可以比較簡單的從一大堆數字之中,篩選出質數來,這方法被稱作厄拉多塞篩法(Sieve of Eeatosthese)

具體操作:先將 2~n 的各個數放入表中,然後在2的上面畫一個圓圈,然後劃去2的其他倍數;第一個既未畫圈又沒有被劃去的數是3,將它畫圈,再劃去3的其他倍數;現在既未畫圈又沒有被劃去的第一個數 是5,將它畫圈,並劃去5的其他倍數……依次類推,一直到所有小於或等於 n 的各數都畫了圈或劃去為止。這時,表中畫了圈的以及未劃去的那些數正好就是小於 n 的素數。

其實,當你要畫圈的素數的平方大於 n 時,那麼後面沒有劃去的數都是素數,就不用繼續判了。如下圖:

python改進版:

從上面的厄拉多塞篩法可以看出,我們只需遍歷[2,這裡寫圖片描述],因為超過這裡寫圖片描述部分如果不是素數,則作為因子在前面的數已經被刪除了。同時這裡利用了python裡list的特性[::i]取i的倍數。

def countPrimes(self, n):
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)

相關文章

程式語言 最新文章