如何在 Python 中实现一个高效的无限素数生成器？

Question

这不是作业，我只是好奇。

无限是这里的关键词。

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

所以，答案不能像“做一个筛子”那样天真。

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

我更喜欢非并发方法。

感谢您阅读（和写作 ;)）！

原文由 Hamish Grubijan 发布，翻译遵循 CC BY-SA 4.0 许可协议

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 避免了一半的步骤以及奇数测试。

erat3

如果不介意多花点心思， erat2 可以通过以下更改加快 35-40%（注意：需要 Python 2.7+ 或 Python 3+，因为 itertools.compress 功能）：

 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 函数利用了所有素数（2、3、5 除外）模 30 结果只有八个数字： MODULOS frozenset 中包含的那些。因此，在产生最初的三个素数后，我们从 7 开始， 只 处理候选素数。

候选过滤使用 itertools.compress 函数； “魔术”在 MASK 序列中； MASK 有 15 个元素（每 30 个数字中有 15 个奇数，由 itertools.islice 函数选择）和 1 开始7. 循环按照 itertools.cycle 函数的指定重复。

候选过滤的引入还需要修改： or (x%30) not in MODULOS 勾选。 erat2 算法处理了所有奇数；既然 erat3 算法只处理 r30 个候选者，我们需要确保所有 D.keys() 只能是这样的“假”候选者。

基准

结果

在 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

原文由 tzot 发布，翻译遵循 CC BY-SA 2.5 许可协议