Eratosthenes筛子-查找素数Python [英] Sieve of Eratosthenes - Finding Primes Python

问题描述

请澄清一下，这不是作业问题:)

Just to clarify, this is not a homework problem :)

我想为正在构建的数学应用找到素数.遇到了 Eratosthenes筛子 方法.

I wanted to find primes for a math application I am building & came across Sieve of Eratosthenes approach.

我已经用Python编写了它的实现.但这太慢了.可以说，如果我想找到所有小于200万的素数.耗时> 20分钟. (我在这一点上将其停止了).我该如何加快速度?

I have written an implementation of it in Python. But it's terribly slow. For say, if I want to find all primes less than 2 million. It takes > 20 mins. (I stopped it at this point). How can I speed this up?

def primes_sieve(limit):
    limitn = limit+1
    primes = range(2, limitn)

    for i in primes:
        factors = range(i, limitn, i)
        for f in factors[1:]:
            if f in primes:
                primes.remove(f)
    return primes

print primes_sieve(2000)

更新: 我最终对此代码进行了分析&发现从列表中删除元素花费了很多时间.考虑到必须遍历整个列表(最坏的情况)才能找到元素&，这是完全可以理解的.然后将其删除，然后重新调整列表(也许会继续复制?).无论如何，我掏出了字典的清单.我的新实现-

UPDATE: I ended up doing profiling on this code & found that quite a lot of time was spent on removing an element from the list. Quite understandable considering it has to traverse the entire list (worst-case) to find the element & then remove it and then readjust the list (maybe some copy goes on?). Anyway, I chucked out list for dictionary. My new implementation -

def primes_sieve1(limit):
    limitn = limit+1
    primes = dict()
    for i in range(2, limitn): primes[i] = True

    for i in primes:
        factors = range(i,limitn, i)
        for f in factors[1:]:
            primes[f] = False
    return [i for i in primes if primes[i]==True]

print primes_sieve1(2000000)

推荐答案

您没有完全实现正确的算法:

You're not quite implementing the correct algorithm:

在您的第一个示例中，primes_sieve并不维护要触发/取消设置的素数标志的列表(如算法中一样)，而是连续调整整数列表的大小，这非常昂贵:从列表需要将所有后续项目下移一个.

In your first example, primes_sieve doesn't maintain a list of primality flags to strike/unset (as in the algorithm), but instead resizes a list of integers continuously, which is very expensive: removing an item from a list requires shifting all subsequent items down by one.

在第二个示例中，primes_sieve1维护素数标志的 dictionary ，这是朝着正确方向迈出的一步，但它以未定义的顺序遍历字典，并多余地删除了以下因素因子(而不是仅使用素数的因子，如算法中那样).您可以通过对键进行排序并跳过非质数(这已经使其速度提高了一个数量级)来解决此问题，但是直接使用列表仍然更加有效.

In the second example, primes_sieve1 maintains a dictionary of primality flags, which is a step in the right direction, but it iterates over the dictionary in undefined order, and redundantly strikes out factors of factors (instead of only factors of primes, as in the algorithm). You could fix this by sorting the keys, and skipping non-primes (which already makes it an order of magnitude faster), but it's still much more efficient to just use a list directly.

正确的算法(使用列表而不是字典)看起来像这样:

The correct algorithm (with a list instead of a dictionary) looks something like:

def primes_sieve2(limit):
    a = [True] * limit                          # Initialize the primality list
    a[0] = a[1] = False

    for (i, isprime) in enumerate(a):
        if isprime:
            yield i
            for n in range(i*i, limit, i):     # Mark factors non-prime
                a[n] = False

(请注意，这还包括从素数平方(i*i)而不是其双数开始的非素数标记的算法优化.)

(Note that this also includes the algorithmic optimization of starting the non-prime marking at the prime's square (i*i) instead of its double.)

这篇关于Eratosthenes筛子-查找素数Python的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！