python - 如何在这个素数筛子的 for 循环中花费更少的时间？

Question

下面所示的埃拉托斯特尼筛法的实现效率非常低。我对找到最有效的方法不感兴趣；我只是想让我已经做得更好。

我知道有很多不同的方法可以做到这一点；我刚刚实现了这个筛子，我的问题是我想知道我能做些什么来使这个特定实现的一个特定部分更加高效。

def sieve(x):
    l = []
    for i in range(x + 1):
        l.append(i)
    l.remove(0)
    l.remove(1)
    clone = l[:]
    test = 0
    for i in l:
        while test < len(clone):
            checker = clone[test]
            if checker % i == 0 and i != checker and i < checker:
                clone.remove(checker)
            test += 1
        test = 0
    return clone
print(sieve(24))

如果将上面的代码粘贴到 http://pythontutor.com/visualize.html#mode=edit 中并逐步执行，您会注意到它已经在第 200 步之前找到了所有素数；它主要浪费时间来完成外部 for 循环的长度。那么操作问题是这样的:在这个特定的实现中，如何减少它在 for 循环中花费的时间？高效的方法是将 clone[test] 的四个实例替换为对 checker 的单个赋值(好吧，无论如何，每个循环都有一个赋值)。

Answer 1

首先，将元素标记为已删除(在已知位置进行单一赋值)比使用list.remove(需要搜索列表)更有效并移动被删除后的每个元素)。然后你可以在最后一次将它们全部过滤掉。就像您已经做的那样，从 0 到 x 的索引从素数开始:

l = [True] * (x + 1)

然后你将一些标记为非素数:

l[0] = False
l[1] = False

那么你可以简化内部循环，每次向前移动固定数量的元素:

for i in range(2, x + 1):
    if not l[i]:
        continue

    for j in range(i * i, x + 1, i):
        l[j] = False

从 i * i 开始，因为当循环命中 时，s * i 形式的 i 的任何较小倍数都已被覆盖>s。这还有一个优点是不涉及除法运算。

使用指示给定索引是否为素数的 bool 值列表来创建素数列表，然后:

return [i for i in range(x + 1) if l[i]]

这一切并没有减少外循环的迭代次数，但它应该已经快了很多，并且使用简化版本也许可以更容易地看到当 i * i 时如何停止 比列表大，并且也跳过检查每个偶数。