嘗試計算Eratosthenes的篩子

我是python的絕對新手，但我試圖計算一些應該像Eratosthenes的篩子那樣的東西。嘗試計算Eratosthenes的篩子

我要開始容易，只需創建一組與2的所有整數高達100讓我們調用集合S

然後我想創建一個所有整數N個這樣的2n是包含在該集合中，我們稱之爲P1。換句話說，一組整數2,4,6,8等

我想然後做同樣的事情，但P2 = 3n，然後P3 = 5n。

最後我想返回我的集合S的所有整數，但忽略P1，P2和P3中的整數。

我該如何繼續這樣做？

我嘗試：

numbers=set(range(2,100))

，但我卡上創建其他組和無視他們！

謝謝。

我的想法至今：

def sieve(n): 
    S = set(range(2, 100)) 
    P1 = set(range(0, 100, 2)) 
    P2 = set(range(0, 100, 3)) 
    P3 = set(range(0, 100, 5)) 
    P5 = set(range(0, 100, 7)) 
    return S-P1-P2-P3-P5 
print (sieve(100))

來源

2014-01-21 user3200098

嘗試'範圍（2，100，2）'，'範圍（3，100， 3）'等等。第三個參數是這個步驟。 –

我該如何丟棄集合？ – user3200098

抽象集。 'S - P1'等。 – Hyperboreus

這裏用回答您的具體問題的一個片段（不是整個篩）：

S = set(range(2, 101)) #numbers 2 to 100 
P1 = set(range(2, 101, 2)) #2n 
P2 = set(range(3, 101, 3)) #3n 
P3 = set(range(5, 101, 5)) #5n 
print ('S = ', S) 
print ('P1 = ', P1) 
print ('P2 = ', P2) 
print ('P3 = ', P3) 
S = S - P1 - P2 - P3 #Here comes the "discarding" 
print ('S = ', S)

顯然，你不會想死您Px的套，並且您將希望通過查看下一個尚未存儲的號碼來識別下一個引物。

來源

2014-01-21 20:44:12 Hyperboreus

我的代碼工作正常，直到我做了一個P4 =設置（範圍（0，100，7）），然後整個序列被擰緊。怎麼來的？是不是應該刪除7,14,21等？ – user3200098

我把我的代碼編輯到目前爲止。 – user3200098

它應該是範圍（7，100，7）而不是範圍（0，100，7）。 – Hyperboreus

range函數接受第三個參數：該步驟。例如，range(2, 10, 3)是[2, 5, 8]。您可以使用它來構建一些數字的倍數集，例如range(3, 100, 3)爲小於100的3的倍數，包括3本身。

結合那些與-操作上套建篩的第一，天真版本：

p = set(range(2, 100)) 
for i in range(2, 10): 
    p = p - set(range(i, 100, i)) 
print sorted(p)

然而，這也將刪除測試i s ^據爲己有，因此缺乏前幾個質數：

[11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, ...]

修復這個算法留給讀者練習。 ;-)

來源

2014-01-21 20:44:22

可以試試這個：

def filter_primes(alist, newlist): 
    for x in alist[1:]: 
     if x%alist[0] != 0: 
      newlist.append(x) 
    return newlist 

alist = range(2, 100) 
sieve_list = [] 
primes = [2] 

while len(alist) > 1: 
    a = filter_primes(alist, sieve_list) 
    primes.append(a[0]) 
    alist = sieve_list 
    sieve_list = [] 

print primes 

Out[1]: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 
67, 71, 73, 79, 83, 89, 97]

應該對任何數量的工作，而不僅僅是100

來源

2014-01-22 19:37:21 gobrewers14

嘗試計算Eratosthenes的篩子

回答

相關問題