我試圖找到所有在python下的200萬以下的素數總和

-5

ls = [] 
total = 0 

for i in range(0,2000000): 
    ls.append(i) 

for i in range(2,2000000): 
    for x in range(2,int(float(2000000/i)+0.5)): 
     ls[int(float(i*x))] = 0 
ls[1] = 0 

for j in range(0,2000000): 
    total += ls[j] 
print total

這段代碼給了我錯誤的答案。它包含大量不是素數的數字。它包含25個以上的數字，而不是素數。我試圖找到所有在python下的200萬以下的素數總和

來源

2014-11-04 Andrew Parkerson

你正在做大量'float'到'int'的轉換。這些都受到一些舍入誤差。如果可能的話，我會嘗試儘可能使用'int'。 – 2014-11-04 16:47:47

你的算法給出錯誤的結果，無法弄清楚你用什麼方法，它會更好，如果你能提供更多的細節。

有一個稱爲篩埃拉托色尼算法有效地生成素數的算法。你發現算法解釋in this thread，用細節來寫的算法。

import math 
def primeNumbers(n): 
    A = range(2, n + 1) 
    B, C= [],A 
    while C[0]< math.sqrt(n): 
     firstElement= C[0] 
     B+= [firstElement] 
     C= [x for x in C if x%firstElement!=0] 
    return B+C 

t= sum(primeNumbers(2000000)) #you summ the prime numbers numbers 
print t

來源

2014-11-04 17:04:29

問題是這一行：

for x in range(2,int(float(2000000/i)+0.5)):

浮置（200萬/ I）並沒有做太多在這種情況下，你的意思是浮動（2000000）/ I？你仍然在進行整數除法，然後將結果轉換爲浮點數。所以，當我是947時，這將返回2111.0而不是2111.93。因此，加上0.5並且調用int（）實際上什麼也不做，並且你仍然以2111結束。

然後這會結束運行循環直到2110，所以你不能標記947 * 2111，這會給你一個誤報。

您可以重寫循環稍微解決這個問題：

for i in range(2,2000000): 
    for x in range(2 * i, 2000000, i): 
     ls[x] = 0

這種方式，而不是分裂，然後相乘，你只是經歷和標記我的所有的倍數，直到2000000

顯然，還有其他（更好的）方法可以解決問題，但我只想指出如何改進當前的解決方案。

來源

2014-11-06 02:16:26 linus

我試圖找到所有在python下的200萬以下的素數總和

回答

相關問題