編輯：已經意識到在SO上有很多優化,但很少有其他人為主篩算法解釋它們,因此很難讓初學者或第一次算法創建者接近它們.所有解決方案都將在python中,以便在速度和優化的同一頁面上.這些解決方案將逐漸變得更快,更復雜. 🙂

香草溶液

def primesVanilla(n):

r = [True] * n

r[0] = r[1] = False

for i in xrange(n):

if r[i]:

for j in xrange(i+i,n,i):

r[j]=False

return r

這是Sieve非常簡單的實現.在繼續之前,請確保您了解上面發生的事情.唯一需要注意的是你在i i而不是i開始標記not-primes,但這很明顯. (因為你認為我本身就是一個素數).為了使測試公平,所有數字將高達2500萬.

real 0m7.663s

user 0m7.624s

sys 0m0.036s

次要改進1(平方根)：

我將嘗試根據直接向不太直接的變化對它們進行排序.注意我們不需要迭代到n,而只需要上升到n的平方根.原因是n下的任何復合數必須具有低于或等于n的平方根的素因子.當你手工篩選時,你會注意到n的平方根上的所有“未被發現”的數字都是默認的素數.

另一個注意事項是,當平方根變成一個整數時,你必須要小心一點,所以你應該在這種情況下添加一個,以便它覆蓋它. IE,在n = 49時,你想循環到7(包括7),或者你可能得出結論49是素數.

def primes1(n):

r = [True] * n

r[0] = r[1] = False

for i in xrange(int(n**0.5+1)):

if r[i]:

for j in xrange(i+i,n,i):

r[j]=False

return r

real 0m4.615s

user 0m4.572s

sys 0m0.040s

請注意,它要快得多.當你考慮它時,你只是循環到平方根,所以現在需要2500萬頂級迭代只有5000頂級.

次要改進2(跳過內循環)：

觀察在內循環中,我們可以從i * i開始,而不是從i i開始.這是從平方根的一個非常相似的論證得出的,但是最大的想法是i和i * i之間的任何復合都已經被較小的素數標記.

def primes2(n):

r = [True] * n

r[0] = r[1] = False

for i in xrange(int(n**0.5+1)):

if r[i]:

for j in xrange(i*i,n,i):

r[j]=False

return r

real 0m4.559s

user 0m4.500s

sys 0m0.056s

那有點令人失望.但是,嘿,它仍然更快.

一些重大改進3(甚至跳過)：

這里的想法是我們可以預先標記所有偶數索引,然后在主循環中跳過迭代2.之后我們可以在3開始外循環,內循環可以跳過2 * i. (因為我改為暗示它會是偶數,(我)(我是我)等)

def primes3(n):

r = [True] * n

r[0] = r[1] = False

for i in xrange(4,n,2):r[i]=False

for i in xrange(3,int(n**0.5+1),2):

if r[i]:

for j in xrange(i*i,n,2*i):

r[j]=False

return r

real 0m2.916s

user 0m2.872s

sys 0m0.040s

酷改進4(wim的想法)：

此解決方案是一個相當高級的技巧.切片分配比循環更快,因此使用python的切片表示法. [R [開始：結束：跳過]

def primes4(n):

r = [True] * n

r[0] = r[1] = False

r[4::2] = [False] * len(r[4::2])

for i in xrange(3,int(1 + n**0.5),2):

if r[i]:

r[i*i::2*i] = [False] * len(r[i*i::2*i])

return r

10 loops, best of 3: 1.1 sec per loop

輕微改進5

請注意,python在計算長度時會復制r [4 :: 2],因此這需要相當多的額外時間,因為我們需要的只是計算長度.我們確實使用了一些討厭的數學來實現這個目標.

def primes5(n):

r = [True] * n

r[0] = r[1] = False

r[4::2] = [False] * ((n+1)/2-2)

for i in xrange(3,int(1 + n**0.5),2):

if r[i]:

r[i*i::2*i] = [False] * ((n+2*i-1-i*i)/(2*i))

return r

10 loops, best of 3: 767 msec per loop

分配加速(Padraic Cunningham)

請注意,我們為所有True分配一個數組,然后將half(均勻)設置為False.實際上我們可以從一個交替的布爾數組開始.

def primes6(n):

r = [False,True] * (n//2)+[True]

r[1],r[2]=False, True

for i in xrange(3,int(1 + n**0.5),2):

if r[i]:

r[i*i::2*i] = [False] * ((n+2*i-1-i*i)/(2*i))

return r

10 loops, best of 3: 717 msec per loop

不要引用我這個,但我認為沒有一些討厭的數學方法,這個最后版本沒有明顯的改進.我嘗試過的一個可愛的屬性,但結果并不快,注意到2,3以外的素數必須是6k 1或6k-1的形式. (注意,如果它是6k,那么可以被6,6k 2 | 2,6k 3 | 3,6k 4 | 2,6k 5整除與-1 mod 6一致.這表明我們每次可以跳過6并檢查兩者無論是從我身邊的糟糕實施,還是蟒蛇內部,我都無法找到任何有意義的速度提升.:(

總結

以上是生活随笔為你收集整理的python列表生成器二维筛选_如何加速Eratosthenes python列表生成器的筛选的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。