在python中使用字典的eratosthenes的篩子

Question

以下是兩種形式的Eratosthenes的篩子。

---

1）首先是我解釋怎麼看這個汗學院的視頻（https://www.khanacademy.org/computing/computer-science/cryptography/comp-number-theory/v/sieve-of-eratosthenes-prime-adventure-part-4）該算法採用模塊化分工時篩編程方式。

---

2）第二個具有一些修改我已經做加快算法包括：使用字典並使用乘法找到複合材料，而不是模塊劃分測試它們從字典刪除的複合元件，然後創建篩選結束後的排序列表。

第二種方法要快得多，但我不得不添加一個try語句，以避免函數嘗試刪除已被刪除的值的情況，但仍會刪除以前的數字的倍數爲尚未刪除。

問題是，有沒有什麼辦法可以避免已經發現複合的值，而不是使用try語句來跳過它們，同時仍然使用乘法來定位複合？

def Sieve_2_b(b): 
     seq_primes=list() 
     c=0 
     for i in range(2,(1+b)): 
      seq_primes.append(i) 
     while (seq_primes[c]**2)<b: 
      k=c 
      while k<(len(seq_primes)): 
       if seq_primes[k]>=(seq_primes[c]**2): 
        if seq_primes[k]%seq_primes[c]==0: 
         del seq_primes[k] 
         k-=1 
       k+=1 
      c+=1 
     return seq_primes 

    def Sieve_2_b_using_dict(b): 
     seq_primes=list() 
     sieve_dict=dict() 
     c=0 
     for i in range(2,(1+b)): 
      seq_primes.append(i) 
      sieve_dict[i]=0 
     while (seq_primes[c]**2)<b: 
      k=c 
      while seq_primes[k]<=(b/seq_primes[c]): 
       try: 
        del(sieve_dict[(seq_primes[k]*seq_primes[c])]) 
       except: 
        print(seq_primes[k],seq_primes[c],'stop this') 
        pass 
       k+=1 
      c+=1 
     seq_primes=sorted(sieve_dict,key=sieve_dict.get) 
     return seq_primes 

Answer 1

你的字典每個鍵存儲無用的價值---這是總是0（這也使得它sorted一個糟糕的鍵）。改用集合。

作爲一種獎勵，集合有一種方法可以刪除元素而不是引發異常，而不管元素在集合中的存在。

這是我的第一個版本，主要是複製&從您的代碼粘貼：

def sieve_using_set(b): 
    seq_primes=list(range(2, b + 1)) 
    sieve_set=set(range(2, b + 1)) 
    c=0 
    while (seq_primes[c]**2)<b: 
     k=c 
     while seq_primes[k]<=(b/seq_primes[c]): 
      sieve_set.discard(seq_primes[k] * seq_primes[c]) 
      k+=1 
     c+=1 
    return list(sorted(sieve_set)) 

它也快得多。速度不受I/O的影響（我在「字典」函數中註釋掉print聲明），也不會因超出的刪除項目而受到影響，因爲設置版本會嘗試刪除字典版本所做的相同值。設置的版本有一個巨大的優勢，它不需要嘗試除外塊使這些超額刪除。

我發現的下一個最大的節省是使用range，而不是經常比較c或k來進行一些計算。我在文件的頂部爲此增加了一個import math：

def sieve_using_set_and_ranges(b): 
    seq_primes=list(range(2, b + 1)) 
    sieve_set=set(range(2, b + 1)) 
    for c in range(0, math.floor(math.sqrt(b)) + 1): 
     for k in range(c, math.floor(b/seq_primes[c]) + 1): 
      sieve_set.discard(seq_primes[k] * seq_primes[c]) 
    return list(sorted(sieve_set)) 

這裏是timeit.Timer.timeit在1000個1000長篩的運行結果，使用舊的安裝的Python 3.1：

Sieve using modular division: 
5.98897910118 
Sieve using dictionary: 
5.10295796394 
Sieve using set: 
3.10129499435 
Sieve using set and ranges: 
1.69016003609 

我使用了一個斷言來證明設置版本產生了與你的兩個函數相同的列表輸出。