如何在Python中高效生成无限素数流？-Python教程-PHP中文网

如何在Python中高效生成无限素数流？

Linda Hamilton

发布： 2024-12-06 21:55:16

原创

414 人浏览过

How to Efficiently Generate an Infinite Stream of Prime Numbers in Python?

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

生成无限素数级数的有效方法是使用埃拉托斯特尼筛法，它通过迭代标记非素数的倍数来消除非素数。虽然这种方法很有效，但它需要大量内存来存储标记的数字。

erat2

这是 Python 标准库说明书中的 erat2 函数，可以是用于生成无穷级数的素数数字：

import itertools as it
def erat2( ):
    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&amp;1):
            #     x += p
            # changed into:
            x = q + 2*p
            while x in D:
                x += 2*p
            D[x] = p

登录后复制

erat2a

erat2 函数可以通过避免不必要的检查来进一步优化：

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&amp;1):
            #     x += p
            # changed into:
            x = q + 2*p
            while x in D:
                x += 2*p
            D[x] = p

登录后复制

erat3

为了获得更快的性能，erat3 函数需要优点是所有素数（2、3 和 5 除外）模 30 只得出八个特定数字。这显着减少了筛选过程中所需的检查数量：

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

登录后复制

这些优化可以显着提高性能，尤其是在生成较大素数时。

以上是如何在Python中高效生成无限素数流？的详细内容。更多信息请关注PHP中文网其他相关文章！