时间戳

首页 > 解决方案 > 我的埃拉托色尼筛法是否正确实施？（Python）

python - 我的埃拉托色尼筛法是否正确实施？（Python）

问题描述

我需要生成大量素数，但是使用 Eratosthenes 筛需要很长时间。目前，生成 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

我错过了一些明显的东西吗？我怎样才能提高筛子的性能？

标签： pythonsieve-of-eratosthenes

解决方案

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

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)，但与更大的问题（即迭代器）相比，这样的小改进是无关紧要的。

推荐阅读