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

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倍，因为它与第一个版本完全相同，只是变量必须遍历一个较短的列表。你知道吗

我正试图找到一种比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):

这个简单的更改将N = 100的测试数减少到87，将N = 500的测试数减少到907。你知道吗