如何在Python中实现一个有效的素数数字生成器？

2018-07-01 01:24:19

这不是一项家庭作业，我只是好奇。

INFINITE是这里的关键词。

我希望将它用作primes（）中的p。我相信这是Haskell中的一个内置函数。

所以，答案不能像“只是做一个筛子”那样幼稚。

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

我更喜欢非并发方法。

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

我仍然喜欢我在这里写的东西（与其他许多作者合作的食谱） - 它显示了Eratosthenes的筛子没有内在的限制，我相信评论和讨论很清楚。最近在Stack Overflow上讨论了这个问题（我猜想搜索作者的名字），有人提出了一个更快的（但恕我直言不太清楚）版本;-)。

“如果我看得更远......”

食谱中的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 ， 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函数利用了以下事实：所有的素数（除erat3以外）以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

由于OP要求有效的实现，下面是David Eppstein / Alex Martelli在活跃状态2002代码中的一个重大改进（在他的答案中可以看到）： 不要在字典中记录prime的信息，直到它看到候选人 。对于产生的n个素数（π（sqrt（n log n））〜2 sqrt（n log n）/ log（n log n）〜2，将空间复杂度降至O（sqrt（n） 2 sqrt（n / log n））。因此，时间复杂度也得到改善，即运行速度更快。

创建一个“滑动筛”作为每个基本素数的当前倍数（即，低于当前生产点的sqrt）的字典，以及它们的步数值：

from itertools import count
                                         # ideone.com/aVndFM
def postponed_sieve():                   # postponed sieve, by Will Ness      
    yield 2; yield 3; yield 5; yield 7;  # original code David Eppstein, 
    sieve = {}                           #   Alex Martelli, ActiveState Recipe 2002
    ps = postponed_sieve()               # a separate base Primes Supply:
    p = next(ps) and next(ps)            # (3) a Prime to add to dict
    q = p*p                              # (9) its sQuare 
    for c in count(9,2):                 # the Candidate
        if c in sieve:               # c's a multiple of some base prime
            s = sieve.pop(c)         #     i.e. a composite ; or
        elif c < q:  
             yield c                 # a prime
             continue              
        else:   # (c==q):            # or the next base prime's square:
            s=count(q+2*p,2*p)       #    (9+6, by 6 : 15,21,27,33,...)
            p=next(ps)               #    (5)
            q=p*p                    #    (25)
        for m in s:                  # the next multiple 
            if m not in sieve:       # no duplicates
                break
        sieve[m] = s                 # original test entry: ideone.com/WFv4f

（这里较旧的原始代码被编辑以包含Tim Peters在下面的答案中看到的变化）。有关相关讨论，另请参阅本文。

类似的2-3-5-7基于轮子的代码运行速度加快了2.15倍（这非常接近3/2 * 5/4 * 7/6 = 2.1875的理论改进）。

链接地址: http://www.djcxy.com/p/86623.html

上一篇: How to implement an efficient infinite generator of prime numbers in Python?

下一篇: Speed up bitstring/bit operations in Python?