當我嘗試記憶時，爲什麼我的代碼更慢？

Question

我有一個功能，列出小於N的素數：

def ListPrimes(N): 
    list = [2] 
    for n in range(3, N, 2): 
     for i in range(3, int(sqrt(n)+1)): 
      if n % i == 0: 
       break 
     else: 
      list.append(n) 
    return list 

我試圖使它更快，所以我改變一行到以下幾點：

def ListPrimesFaster(N): 
    list = [2] 
    for n in range(3, N, 2): 
     for i in list: 
      if n % i == 0: 
       break 
     else: 
      list.append(n) 
    return list 

我感到驚訝的是，第二個版本至少慢5倍，因爲它與第一個版本相同，只是變量i必須遍歷較短的列表。

我試圖找到一種更快的方式列出質數比一些N.

Answer 1

ListPrimesFaster()不會通過更短的列表中搜索更小，因爲它包括在list是比sqrt(n)更高的元素。 list的尺寸比sqrt(n)增長得更快，並且從3開始的範圍也保存了幾個步驟。 ListPrimes(100)執行139n % i == 0測試，而ListPrimesFaster(100)確實362。當N爲500時，測試計數爲1616與4933。

順便說一句，在ListPrimes()，內環只需要考奇的因素，因爲n總是奇數，所以你可以將其更改爲：

for i in range(3, int(sqrt(n)+1), 2): 

這個簡單的變化下降的測試數量87爲N = 100和907的N = 500。