我如何在这个素数筛选器的 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 时，s * i 形式的 i 的任何更小的倍数已经被覆盖。这也有不涉及除法运算的优点。

使用指示给定索引是否为素数的布尔值列表来制作素数列表，然后：

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

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

我如何在这个素数筛选器的 for 循环中花费更少的时间？

How do I spend less time in the for loop in this prime number sieve?

python

performance

for-loop

sieve-of-eratosthenes