Python에서 효율적인 소수 생성을 위해 에라토스테네스의 체를 어떻게 최적화할 수 있습니까?

에라토스테네스의 체: Python에서 소수 생성 최적화

에라토스테네스의 체는 소수를 찾는 고전적인 알고리즘입니다. 그러나 성능 병목 현상을 방지하려면 올바르게 구현하는 것이 중요합니다.

원래 구현

제공된 primes_sieve 함수는 후보 소수 목록을 유지하고 비 소수를 반복적으로 제거합니다. 목록을 순회하고 요인을 제거하여 소수를 만듭니다. 이 접근 방식은 목록 조작 비용이 높기 때문에 본질적으로 비효율적입니다.

사전 기반 최적화

향상된 primes_sieve1 함수는 사전을 사용하여 소수 플래그를 저장합니다. 목록 기반 접근 방식보다 빠르지만 여전히 문제에 직면해 있습니다. 정의되지 않은 순서로 사전을 반복하여 주요 요소가 아닌 요소를 중복 표시합니다. 또한 최종 사전을 목록으로 변환하므로 불필요한 오버헤드가 발생합니다.

정확하고 효율적인 구현

올바른 에라토스테네스의 체 알고리즘은 부울 플래그 목록을 활용하여 소수성을 나타냅니다. primes_sieve2 함수는 모든 숫자에 대해 플래그를 True로 초기화하고 0과 1에 대한 플래그를 False로 설정합니다. 목록을 반복하면서 플래그를 False로 설정하여 소수가 아닌 항목을 표시합니다.

이 접근 방식은 다음과 같은 이유로 효율적입니다.

• 오버헤드를 방지하고 사전 대신 목록을 사용합니다. 키-값 연산.
• 소인수만 소수가 아닌 것으로 표시하여 중복을 줄입니다.
• 각 소수의 더블이 아닌 제곱에서 시작하여 마킹 프로세스를 최적화합니다.

에라토스테네스의 체를 올바르게 구현하면 소수 생성 기능을 제공하므로 2백만 개 미만의 소수를 찾는 등 입력 제한이 큰 경우에도 적합합니다.

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