python - 当我尝试内存时，为什么我的代码会变慢？

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)执行139 n % 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 .