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

Python에서 에라토스테네스의 체를 사용하여 소수 생성 최적화

에라토스테네스의 체는 지정된 한도까지 소수를 식별하는 유서 깊은 알고리즘입니다. 구현하기는 쉽지만 큰 제한에 대해서는 놀라울 정도로 느릴 수 있습니다.

느린 구현

다음과 같은 시브의 Python 구현은 효율성 문제에 직면합니다.

def primes_sieve(limit):
    primes = range(2, limit+1)

    for i in primes:
        factors = range(i, limitn, i)
        for f in factors[1:]:
            if f in primes:
                primes.remove(f)

병목 현상은 숫자가 제거됨에 따라 소수 목록의 크기를 계속 조정하는 데 있습니다. Python 목록에서 항목을 제거하려면 후속 요소를 이동해야 하므로 계산 비용이 많이 드는 작업이 됩니다.

사전을 사용한 더 빠른 구현

이 문제를 해결하려면 사전 기반 구현이 필요합니다. 사용할 수 있습니다:

def primes_sieve1(limit):
    primes = dict()
    for i in range(2, limit+1): primes[i] = True

    for i in primes:
        factors = range(i,limitn, i)
        for f in factors[1:]:
            primes[f] = False

이것은 소수 플래그 사전을 유지하여 크기 조정 작업의 필요성을 줄입니다. 그러나 정의되지 않은 순서로 사전 키를 반복하고 소수가 아닌 숫자의 소수가 아닌 요소를 반복적으로 표시하면 효율성이 제한됩니다.

목록을 사용한 수정된 알고리즘

올바른 구현 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 더 자세히 따릅니다:

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

이것은 목록을 유지합니다 소수 플래그를 사용하여 0과 1을 제외한 모든 숫자를 소수로 초기화합니다. 소수의 배수를 소수의 제곱부터 시작하여 소수가 아닌 것으로 표시하여 프로세스를 최적화합니다.

구현 시 효율성 문제를 해결하여, 이 수정된 알고리즘은 큰 제한에서도 소수 생성 속도를 크게 향상시킵니다.

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