試圖在Python中編寫Eratosthenes Sieve。這是正確的，我怎樣才能讓它更快？

可能重複：
Fastest way to list all primes below N in python 試圖在Python中編寫Eratosthenes Sieve。這是正確的，我怎樣才能讓它更快？

我還沒有做編程很長，我只是在做這個爲了好玩，我不知道很多先進的Python，但是... 我寫了這個，我想知道它是否實際上是一個Eratosthenes Sieve程序，如果是的話，我怎麼能使它更快。我真的不希望有人發佈一個解決方案，但更多的告訴我如何適應我的。

def eratSieve(n): 
    all = [] 
    for a in range(2, n+1): 
     all.append(a)    
    for b in all:      
     for i in range(2,int(round(len(all)/b))): 
      while i*b in all: 
       all.remove(i*b) 
       i+=1 
    return all

感謝您的幫助。

順便說一句 - 這是在Python 2.7

來源

2012-12-14 blueteeth

我想你應該看看[這個問題]（http://stackoverflow.com/questions/2068372/fastest-way-to-list-全素數 - 低於N合蟒蛇）。 :) –

它不工作的權利。

主要問題是您循環使用all和while中的所有值，您從all中刪除某個元素。

這樣在all一些價值不考慮的，所以功能不會刪除所有非素數

嘗試執行對於n = 100，你得到的結果是

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99

而它應該是

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 （從http://en.wikipedia.org/wiki/Prime_number）

此外，第二個for的範圍是錯誤的，因爲您考慮列表的長度，而不是當前值b，因此您僅在前50個值中檢查2的倍數，在第2個值中檢查3的倍數前17名，前9名5名等。從b = 13你從來沒有在內部for進入，因爲int(round(len(all)/b)) = 1等你像for i in range(2,1)

來源

2012-12-14 14:14:03 Gianluca

-1

def primes(N): 
    primes = [x for x in (2, 3, 5, 7, 11, 13) if x < N] 
    if N < 17: return primes 
    candidators = [x for x in xrange((N - 2) | 1, 15, -2) 
        if x % 3 and x % 5 and x % 7 and x % 11 and x % 13] 
    top = int(N ** 0.5) 
    while (top + 1) * (top + 1) <= N: top += 1 
    while True: 
     p = candidators.pop() 
     primes.append(p) 
     if p > top: break 
     candidators = filter(p.__rmod__, candidators) 
    candidators.reverse() 
    primes.extend(candidators) 
    return primes

我覺得這個代碼將運行得更快......

來源

2012-12-14 14:10:10

我贊布羅塔同意，我有一個可能的解決方案：讓你的主陣列（all）爲布爾變量和標記非質數，但不要刪除它們。它可能也會更快，因爲您不會更改列表大小。

次要的事情：如果您想保留爲整數，您可以在開頭只寫all = range(2, n+1)。

來源

2012-12-14 14:52:04 Serpens

您的方法會產生不正確的結果。錯誤在於for i循環。在這裏，它是調整，並與測試：

known_primes = [ 
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,101,103,107,109,113, 
127,131,137,139,149,151,157,163,167,173, 
179,181,191,193,197,199,211,223,227,229, 
233,239,241,251,257,263,269,271,277,281, 
283,293,307,311,313,317,331,337,347,349, 
353,359,367,373,379,383,389,397,401,409, 
419,421,431,433,439,443,449,457,461,463, 
467,479,487,491,499,503,509,521,523,541, 
547,557,563,569,571,577,587,593,599,601, 
607,613,617,619,631,641,643,647,653,659, 
661,673,677,683,691,701,709,719,727,733, 
739,743,751,757,761,769,773,787,797,809, 
811,821,823,827,829,839,853,857,859,863, 
877,881,883,887,907,911,919,929,937,941, 
947,953,967,971,977,983,991,997,1009,1013, 
1019,1021,1031,1033,1039,1049,1051,1061,1063,1069, 
1087,1091,1093,1097,1103,1109,1117,1123,1129,1151, 
1153,1163,1171,1181,1187,1193,1201,1213,1217,1223, 
1229,1231,1237,1249,1259,1277,1279,1283,1289,1291, 
1297,1301,1303,1307,1319,1321,1327,1361,1367,1373, 
1381,1399,1409,1423,1427,1429,1433,1439,1447,1451, 
1453,1459,1471,1481,1483,1487,1489,1493,1499] 
def eratSieve(n): 
    all = [] 
    for a in range(2, n+1): 
     all.append(a)    
    for b in all:      
     for i in all[all.index(b):]: 
      while i*b in all: 
       all.remove(i*b) 
       i+=1 
    return all 

for N in range(1500): 
    for n in eratSieve(N): 
     if n not in known_primes: 
      print N,n

來源

2012-12-14 15:58:28

你確定它工作？'n = 100'的函數'eratSieve'的輸出是'[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,99]' – Gianluca

你是對的，它需要一個「+ 1」的循環。我做了相應的編輯。 –

試圖在Python中編寫Eratosthenes Sieve。這是正確的，我怎樣才能讓它更快？

回答

相關問題