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

erat3

더 빠른 성능을 위해 erat3는 함수는 모듈로 30의 모든 소수(2, 3, 5 제외)가 8개의 특정 숫자만 생성한다는 사실을 활용합니다. 이렇게 하면 선별 프로세스 중에 필요한 확인 횟수가 크게 줄어듭니다.

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!