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

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