当我尝试记忆时，为什么我的代码更慢？

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。