本文介绍了如何在Python中实现有效的质数无限生成器?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

这不是作业，我只是很好奇.

This is not a homework, I am just curious.

INFINITE是这里的关键词.

INFINITE is the key word here.

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

I wish to use it as for p in primes(). I believe that this is a built-in function in Haskell.

因此，答案不能像只做筛子"那样幼稚.

So, the answer cannot be as naive as "Just do a Sieve".

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

First of all, you do not know how many consecutive primes will be consumed. Well, suppose you could concoct 100 of them at a time. Would you use the same Sieve approach as well as the frequency of prime numbers formula?

我更喜欢非并行方法.

谢谢您的阅读(和写作；))！

Thank you for reading (and writing ;) )!

如果我进一步看过……"

食谱中的erat2功能可以进一步加快(大约20-25％):

"If I have seen further…"

The erat2 function from the cookbook can be further sped up (by about 20-25%):

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可以避免一半的步骤以及对奇数的检验.

The not (x&1) check verifies that x is odd. However, since both q and p are odd, by adding 2*p half of the steps are avoided along with the test for oddity.

如果您不介意一些额外的幻想，可以通过以下更改将erat2加快35-40％(注意:由于itertools.compress函数，需要Python 2.7+或Python 3+):

If one doesn't mind a little extra fanciness, erat2 can be sped up by 35-40% with the following changes (NB: needs Python 2.7+ or Python 3+ because of the itertools.compress function):

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为模的质数(除2、3、5外)仅得出8个数字:MODULOS冻结集中包含的那些.因此，在产生了最初的三个素数之后，我们从7开始，仅与候选对象进行 .
候选过滤使用itertools.compress函数；魔术"按MASK顺序； MASK具有15个元素(由itertools.islice函数选择的每30个数字中有15个奇数)，对于每个可能的候选项，均从7开始具有1.循环按itertools.cycle的指定重复功能.
候选过滤的引入还需要另一种修改:or (x%30) not in MODULOS检查. erat2算法处理所有奇数；现在erat3算法仅处理r30个候选，我们需要确保所有D.keys()只能是"false"候选.

The erat3 function takes advantage of the fact that all primes (except for 2, 3, 5) modulo 30 result to only eight numbers: the ones included in the MODULOS frozenset. Thus, after yielding the initial three primes, we start from 7 and work only with the candidates.
The candidate filtering uses the itertools.compress function; the "magic" is in the MASK sequence; MASK has 15 elements (there are 15 odd numbers in every 30 numbers, as chosen by the itertools.islice function) with a 1 for every possible candidate, starting from 7. The cycle repeats as specified by the itertools.cycle function.
The introduction of the candidate filtering needs another modification: the or (x%30) not in MODULOS check. The erat2 algorithm processed all odd numbers; now that the erat3 algorithm processes only r30 candidates, we need to make sure that all D.keys() can only be such —false— candidates.

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

On an Atom 330 Ubuntu 9.10 server, versions 2.6.4 and 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:

On an AMD Geode LX Gentoo home server, Python 2.6.5 and 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功能.以下是测试脚本:

Benchmark code

A primegen.py module contains the erat2, erat2a and erat3 functions. Here follows the testing script:

#!/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

这篇关于如何在Python中实现有效的质数无限生成器?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！

erat2

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

问题描述

推荐答案

如果我进一步看过……"

"If I have seen further…"

基准代码

Benchmark code