python - 为什么我的素数筛返回相同结果的速度比在 Python 2.7 中查找素数的暴力方法慢？

Question

我对 Python 相当陌生，我一直在尝试找到一种快速方法来查找给定数字之前的素数。

当我使用埃拉托斯特尼素数筛法时，代码如下:

#Finding primes till 40000.
import time
start = time.time()
def prime_eratosthenes(n):
    list = []
    prime_list = []
    for i in range(2, n+1):
        if i not in list:
            prime_list.append(i)
            for j in range(i*i, n+1, i):
                list.append(j)
    return prime_list

lists = prime_eratosthenes(40000)
print lists
end = time.time()
runtime = end - start
print "runtime =",runtime

除了包含素数的列表之外，我还得到如下一行作为输出:

runtime = 20.4290001392

根据所使用的 RAM 等，我通常会始终得到 +-0.5 范围内的值。

但是，当我尝试使用暴力方法找到 40000 之前的素数时，如以下代码所示:

import time
start = time.time()
prime_lists = []
for i in range(1,40000+1):
    for j in range(2,i):
        if i%j==0:
            break
    else:
        prime_lists.append(i)
print prime_lists
end = time.time()
runtime = end - start
print "runtime =",runtime

这一次，连同素数列表，我得到了一个较小的运行时间值:

runtime = 16.0729999542

该值仅在 +-0.5 范围内变化。

显然，筛法比蛮力法慢。

我还观察到，两种情况下运行时间之间的差异只会随着值“n”的增加而增加，直到找到素数为止。

任何人都可以对上述行为给出合乎逻辑的解释吗？我期望筛子比蛮力法更有效地发挥作用，但在这里似乎反之亦然。

Answer 1

虽然追加到列表并不是实现该算法的最佳方式(原始算法使用固定大小的数组)，但它是amortized constant time 。我认为一个更大的问题是如果我不在列表中这是线性时间。对于较大的输入，您可以做出的最佳更改是让外部 for 循环仅检查 sqrt(n)，这可以节省大量计算。

更好的方法是保留一个 bool 数组来跟踪删除的数字，就像维基百科关于筛子的文章中所看到的那样。这样，由于是数组访问，因此跳过数字是常数时间。

例如:

def sieve(n):
    nums = [0] * n
    for i in range(2, int(n**0.5)+1):
        if nums[i] == 0:
            for j in range(i*i, n, i):
                nums[j] = 1

    return [i for i in range(2, n) if nums[i] == 0]

因此，为了回答您的问题，您的两个 for 循环使算法可能执行 O(n^2) 工作，而巧妙地处理外部 for 循环使新算法花费 O(n sqrt(n)) 时间(实际上，对于合理大小的 n，运行时间更接近 O(n))