Python에서 더 빠른 소수 생성을 위해 에라토스테네스 체 알고리즘을 어떻게 최적화할 수 있습니까?

에라토스테네스의 체 개선됨: Python 프라임 생성 최적화

에라토스테네스의 체는 미리 정의된 한계까지 소수를 찾는 효율적인 알고리즘입니다. . 그러나 순진한 Python 구현은 더 큰 제한으로 인해 지나치게 느릴 수 있습니다.

병목 현상 식별

제공된 예에서 프로파일링을 통해 요소를 제거하는 데 상당한 시간이 소요되는 것으로 나타났습니다. 목록(소수). 이 작업은 특히 긴 목록의 경우 계산 비용이 많이 듭니다.

목록을 사전으로 대체

이 문제를 해결하기 위한 초기 시도에는 목록을 사전(소수)으로 바꾸는 것이 포함되었습니다. . 이를 통해 더 빠른 요소 제거가 가능해졌습니다. 그러나 알고리즘은 여전히 ​​다음 문제로 인해 어려움을 겪고 있습니다.

• 정의되지 않은 순서로 사전에 대한 반복
• 소수가 아닌 숫자 요소의 중복 표시

올바른 알고리즘 구현

완전히 최적화하려면 알고리즘, 수정이 필요했습니다:

1. 소수 플래그에 사전 대신 목록 사용
2. 소수가 아닌 요소 건너뛰기
3. 소수 플래그에서 인수 표시 시작 2배가 아닌 정사각형

최적화 알고리즘

최적화된 알고리즘(primes_sieve2)은 소수 플래그에 부울 목록을 사용합니다. 1보다 큰 모든 숫자에 대해 목록을 True로 초기화합니다. 그런 다음 목록을 반복하여 소수가 아닌 숫자를 표시합니다.

def primes_sieve2(limit):
    a = [True] * limit                          # Initialize the primality list
    a[0] = a[1] = False

    for (i, isprime) in enumerate(a):
        if isprime:
            yield i
            for n in range(i*i, limit, i):     # Mark factors non-prime
                a[n] = False

이러한 주요 측면을 최적화함으로써 알고리즘은 성능을 크게 향상시켜 다음을 찾습니다. 몇 초 만에 최대 200만개까지 프라이밍됩니다.

위 내용은 Python에서 더 빠른 소수 생성을 위해 에라토스테네스 체 알고리즘을 어떻게 최적화할 수 있습니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!