Eratosthenes的篩子返回大的合成數（這是一個錯誤）

我正在Python中實現Eratosthenes的Sieve。它返回合數附近的搜索範圍的終點：Eratosthenes的篩子返回大的合成數（這是一個錯誤）

def primes_Ero(n=1000): 
    primes = [] 
    a = [True]*(n+1) 
    a[0] = a[1] = False 
    for (i,isprime) in enumerate(a): 
     if isprime: 
      for n in range(i*i,n+1, i):   
       a[n] = False 
      primes.append(i) 
    return primes

當使用更大的數字，Ñ，我最終合數。我做了一個檢查，看看哪些號碼複合（相比於強力法），

鑑於ñ，什麼號碼是複合：

n= 100; [] 
n= 500; [493, 497] 
n= 1000; [961, 989] 
n= 10000; [9701, 9727, 9797, 9853, 9869, 9917, 9943, 9953, 9983, 9991, 9997]

我在做什麼錯？

來源

2017-02-24 LascieL

'if i == 31：'的意圖是什麼？ –

另外，你使用'n'來做兩件事情。 –

@PaulHankin明白了。更改內部for循環中的變量，例如：'對於範圍（i * i，n + 1，i）中的k'：'並且問題消失。 – jas

問題是這樣的線：

for n in range(i*i, n+1, i):

最初n被設置爲參數值（缺省值= 1000），但在for循環執行用於在第一時間經過n將持有i < n < i + n。第二次執行for循環有問題。

您應該重新命名您正在使用的n之一。考慮給它一個合適的名稱，如sieve_size，它更多地描述了它的實際功能。

我想指出的一件事是，雖然你的代碼很聰明，你是修改你正在迭代的列表。這通常被認爲是不好的做法。

來源

2017-02-24 00:33:14

謝謝！我正在編寫一些不同的想法，並忘記將這些部分重新命名爲描述性的。這幫了很多。 – LascieL

對最後一段的評論：在迭代列表時通過索引修改列表的值是沒有問題的。這只是一個問題，如果你插入或從列表中間刪除值（因爲它會更改所有後面的值的索引）。 – Blckknght

Eratosthenes的篩子返回大的合成數（這是一個錯誤）

回答

相關問題