我的埃拉托色尼筛法是否正确实施？ (Python)

Question

我需要生成大量素数，但是使用埃拉托色尼筛法花费的时间太长了。目前，生成 100,000 以下的素数大约需要 3 秒，生成 1,000,000 以下的素数大约需要 30 秒。这似乎表明 O(n) 的复杂性，但据我所知这是不对的。代码：

def generate_primes(limit):
    boolean_list = [False] * 2 + [True] * (limit - 1)
    for n in range(2, int(limit ** 0.5 + 1)):
        if boolean_list[n] == True:
            for i in range(n ** 2, limit + 1, n):
                boolean_list[i] = False

我是不是遗漏了什么明显的东西？如何提高筛子的性能？

Answer 1

循环索引在 Python 中众所周知是一个非常慢的操作。通过用数组切片替换循环，用 Numpy 数组替换列表，我们看到增加了 @ 3x:

import numpy as np
import timeit

def generate_primes_original(limit):
    boolean_list = [False] * 2 + [True] * (limit - 1)
    for n in range(2, int(limit ** 0.5 + 1)):
        if boolean_list[n] == True:
            for i in range(n ** 2, limit + 1, n):
                boolean_list[i] = False
    return np.array(boolean_list,dtype=np.bool)

def generate_primes_fast(limit):

    boolean_list = np.array([False] * 2 + [True] * (limit - 1),dtype=bool)
    for n in range(2, int(limit ** 0.5 + 1)):
        if boolean_list[n]:
            boolean_list[n*n:limit+1:n] = False
    return boolean_list

limit = 1000

print(timeit.timeit("generate_primes_fast(%d)"%limit, setup="from __main__ import generate_primes_fast"))
# 30.90620080102235 seconds

print(timeit.timeit("generate_primes_original(%d)"%limit, setup="from __main__ import generate_primes_original"))
# 91.12803511600941 seconds

assert np.array_equal(generate_primes_fast(limit),generate_primes_original(limit))
# [nothing to stdout - they are equal]

要获得更快的速度，一种选择是使用 numpy vectorization。查看外部循环，如何对其进行矢量化并不是很明显。

其次，如果您移植到 Cython，您将看到显着的加速，这应该是一个相当无缝的过程。

编辑：您可能还会通过更改 n**2 => math.pow(n,2) 之类的东西看到改进，但与更大的问题（即迭代器）相比，这样的小改进是无关紧要的。

Answer 2

如果您仍在使用 Python 2 使用 xrange 而不是 range 以获得更快的速度

我的埃拉托色尼筛法是否正确实施？ (Python)

Is my Sieve of Eratosthenes implemented correctly? (Python)

python

sieve-of-eratosthenes