为什么我的素数筛选 return 相同的结果比在 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

虽然附加到列表不是实现此算法的最佳方式（原始算法使用固定大小的数组），但它是。我认为更大的问题是 if i not in list 这是线性时间。对于更大的输入，您可以做出的最佳更改是让外部 for 循环仅检查 sqrt(n)，这样可以节省大量计算。

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

例如：

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)）

为什么我的素数筛选 return 相同的结果比在 Python 2.7 中寻找素数的蛮力方法慢？

Why does my prime number sieve return the same result slower than the brute force method for finding primes in Python 2.7?

python

primes

python-2.7