如何在Python中实现有效的质数无限生成器？

Question

INFINITE是这里的关键词。

我希望将其用作for p in primes()。我相信这是Haskell中的内置函数。

因此，答案不能像“只做筛子”那样幼稚。

首先，你不知道会消耗多少连续的素数。好吧，假设你一次可以炮制100个。你会使用相同的Sieve方法以及质数频率公式吗？

Answer 1

erat2菜谱中的功能可以进一步加快（大约20-25％）：

erat2a
import itertools as it
def erat2a( ):
    D = {  }
    yield 2
    for q in it.islice(it.count(3), 0, None, 2):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            # old code here:
            # x = p + q
            # while x in D or not (x&1):
            #     x += p
            # changed into:
            x = q + 2*p
            while x in D:
                x += 2*p
            D[x] = p

该not (x&1)检查验证x为奇数。然而，由于这两个 q和p是奇数，通过添加2*p下列步骤一半避免随着测试古怪。

擦除3
如果你不介意一些额外的幻想，erat2可以通过以下更改将速度提高35-40％（注意：由于该itertools.compress功能，需要Python 2.7+或Python 3+ ）：

import itertools as it
def erat3( ):
    D = { 9: 3, 25: 5 }
    yield 2
    yield 3
    yield 5
    MASK= 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0,
    MODULOS= frozenset( (1, 7, 11, 13, 17, 19, 23, 29) )

    for q in it.compress(
            it.islice(it.count(7), 0, None, 2),
            it.cycle(MASK)):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            x = q + 2*p
            while x in D or (x%30) not in MODULOS:
                x += 2*p
            D[x] = p

该erat3函数利用了以下事实：所有以30为模的质数（除MODULOS2、3、5 外）仅得出8个数字：frozenset中包含的那些。因此，在产生最初的三个素数之后，我们从7开始，仅与候选者一起工作。
候选过滤使用该itertools.compress功能；“魔术”按MASK顺序排列；MASK包含15个元素（由itertools.islice函数选择，每30个数字中有15个奇数），1每个可能的候选者都有一个，从7开始。循环按itertools.cycle函数指定的那样重复。
候选过滤的引入需要另一种修改：or (x%30) not in MODULOS检查。erat2算法处理所有奇数；现在该erat3算法仅处理r30个候选对象，因此我们需要确保所有对象D.keys()只能是这样的-false-候选对象。

基准测试

结果

在Atom 330 Ubuntu 9.10服务器上，版本2.6.4和3.1.1+：

$ testit
up to 8192
==== python2 erat2 ====
100 loops, best of 3: 18.6 msec per loop
==== python2 erat2a ====
100 loops, best of 3: 14.5 msec per loop
==== python2 erat3 ====
Traceback (most recent call last):
…
AttributeError: 'module' object has no attribute 'compress'
==== python3 erat2 ====
100 loops, best of 3: 19.2 msec per loop
==== python3 erat2a ====
100 loops, best of 3: 14.1 msec per loop
==== python3 erat3 ====
100 loops, best of 3: 11.7 msec per loop

在AMD Geode LX Gentoo家用服务器上，使用Python 2.6.5和3.1.2：

$ testit
up to 8192
==== python2 erat2 ====
10 loops, best of 3: 104 msec per loop
==== python2 erat2a ====
10 loops, best of 3: 81 msec per loop
==== python2 erat3 ====
Traceback (most recent call last):
…
AttributeError: 'module' object has no attribute 'compress'
==== python3 erat2 ====
10 loops, best of 3: 116 msec per loop
==== python3 erat2a ====
10 loops, best of 3: 82 msec per loop
==== python3 erat3 ====
10 loops, best of 3: 66 msec per loop

基准代码
甲primegen.py模块包含erat2，erat2a和erat3功能。以下是测试脚本：

#!/bin/sh
max_num=${1:-8192}
echo up to $max_num
for python_version in python2 python3
do
    for function in erat2 erat2a erat3
    do
        echo "==== $python_version $function ===="
        $python_version -O -m timeit -c \
        -s  "import itertools as it, functools as ft, operator as op, primegen; cmp= ft.partial(op.ge, $max_num)" \
            "next(it.dropwhile(cmp, primegen.$function()))"
    done
done