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

에라토스테네스의 체 - Python에서 소수 찾기

문제:

구현하는 동안 Python의 Sieve of Eratosthenes 알고리즘을 사용하면 실행 시간이 느려지는 경우가 많습니다. 특히 1백만이 넘는 소수를 검색할 때 그렇습니다.

해결책:

주어진 구현은 여러 가지 개선 영역을 제시합니다.

1. 최적화되지 않은 알고리즘:

• 초기 구현인 primes_sieve는 소수 목록을 유지하므로 요소 제거가 비효율적입니다.
• primes_sieve1은 소수 플래그에 사전을 사용하지만 적절한 반복이 부족합니다. 중복 요소 마킹

2. 목록 조작 비효율성:

• Python 목록에서 요소를 제거하는 것은 후속 요소를 이동해야 하기 때문에 비용이 많이 드는 작업입니다.

최적화된 구현 :

이러한 문제를 해결하려면 다음 최적화된 사항을 고려하세요. 구현:

def primes_sieve2(limit):
    a = [True] * limit
    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

주요 개선 사항:

• 원위 플래그에 직접 목록을 사용하여 비용이 많이 드는 목록 크기 조정을 방지합니다.
• 느리게 생성 필요에 따라 소수를 사용하므로 전체를 저장할 필요가 없습니다. 목록.
• 소수의 제곱에서 시작하여 소수가 아닌 인수를 효율적으로 표시합니다.

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