埃拉托斯特尼筛法 - 用Python找质数

Question

我想澄清一下，这不是一个作业问题 :)

我想为我正在开发的数学应用找到质数，于是我发现了埃拉托斯特尼筛法这个方法。

我用Python写了这个方法的实现。但是速度非常慢。比如说，如果我想找出小于200万的所有质数，竟然需要超过20分钟。（我在这个时候停止了运行）。我该如何加快这个速度呢？

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)

更新： 我对这段代码进行了性能分析，发现花费了很多时间在从列表中删除一个元素上。这是可以理解的，因为它需要遍历整个列表（最坏情况下）来找到这个元素，然后再删除它，最后还要重新调整列表（可能还涉及一些复制操作？）。总之，我把列表换成了字典。我的新实现是 -

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)

Answer 1

从数组（列表）的开头删除元素时，需要把后面的所有元素往前移动。这就意味着，如果你从前面开始一个一个地删除列表中的每个元素，这个过程的复杂度是O(n^2)，也就是说效率很低。

不过，你可以用集合来更高效地完成这个操作：

def primes_sieve(limit):
    limitn = limit+1
    not_prime = set()
    primes = []

    for i in range(2, limitn):
        if i in not_prime:
            continue

        for f in range(i*2, limitn, i):
            not_prime.add(f)

        primes.append(i)

    return primes

print primes_sieve(1000000)

...或者，你也可以选择不需要重新排列列表：

def primes_sieve(limit):
    limitn = limit+1
    not_prime = [False] * limitn
    primes = []

    for i in range(2, limitn):
        if not_prime[i]:
            continue
        for f in xrange(i*2, limitn, i):
            not_prime[f] = True

        primes.append(i)

    return primes

Answer 2

在编程中，有时候我们需要把一些代码放在一起，这样可以让它们更容易管理和使用。比如说，如果你有一段代码需要重复使用，或者你想把一些功能分开，这时候就可以用“函数”来帮忙。函数就像一个小工具箱，你把需要的工具放进去，想用的时候就可以直接拿出来用。

另外，代码中有些地方可能会出现错误，这时候我们需要找到这些错误并修复它们。这个过程叫做“调试”。调试就像是在找拼图的缺口，你需要仔细查看每一块，确保它们都能完美拼在一起。

还有，编程的时候，我们常常需要与其他人合作。这就需要我们写一些文档，说明我们的代码是怎么工作的，别人才能理解和使用。这就像是写一本说明书，让别人知道怎么使用你的工具。

总之，编程就像是在搭建一个大房子，每一块代码都是房子的一部分。我们需要把这些部分合理地组合在一起，才能建造出一个坚固、美观的房子。

def eratosthenes(n):
    multiples = []
    for i in range(2, n+1):
        if i not in multiples:
            print (i)
            for j in range(i*i, n+1, i):
                multiples.append(j)

eratosthenes(100)

Answer 3

你实现的算法有点问题：

在你的第一个例子中，primes_sieve 没有保持一个标记质数的列表来进行标记和取消标记（就像算法中那样），而是不断地调整一个整数列表的大小，这样做开销很大：从列表中删除一个项目需要把后面的所有项目都往前移动一位。

在第二个例子中，primes_sieve1 保持了一个质数标记的 字典，这已经是朝着正确方向迈出了一步，但它以不确定的顺序遍历字典，并且多余地标记了因子的因子（而不是仅仅标记质数的因子，像算法中那样）。你可以通过对键进行排序，并跳过非质数来解决这个问题（这样做会让速度快很多），但直接使用列表会更高效。

正确的算法（用列表而不是字典）大致是这样的：

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）开始标记非质数，而不是从它的两倍开始。）