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

에라토스테네스의 체

에라토스테네스의 체는 고대 알고리즘이지만 오늘날에도 주어진 숫자 아래의 모든 소수를 찾는 간단하고 효율적인 방법으로 여전히 사용되고 있습니다. . 알고리즘은 2부터 시작하여 각 소수의 배수를 반복적으로 표시하는 방식으로 작동합니다.

다음은 에라토스테네스의 체의 Python 구현입니다.

def sieve_of_eratosthenes(n):
    """Return a list of all prime numbers below n."""

    # Create a list of all numbers from 2 to n.
    numbers = list(range(2, n + 1))

    # Iterate over the numbers in the list.
    for i in range(2, int(n ** 0.5) + 1):

        # If the number is prime, mark off all its multiples.
        if numbers[i] != -1:
            for j in range(i * i, n + 1, i):
                numbers[j] = -1

    # Return the list of prime numbers.
    return [i for i in numbers if i != -1]

이 알고리즘은 구현하기가 비교적 간단합니다. 그리고 그것은 매우 효율적입니다. 예를 들어 현대 컴퓨터에서는 약 0.1초 안에 100만 미만의 소수를 모두 찾아낼 수 있습니다.

시간 복잡도

에라토스테네스의 체의 시간 복잡도는 O(n log log n)입니다. . 이는 알고리즘이 2부터 n까지의 모든 수의 목록을 생성하는 데 O(n) 시간이 걸리고, 각 소수의 모든 배수를 표시하는 데 O(log log n) 시간이 걸린다는 것을 의미합니다.

더 빠르게 만들 수 있을까요?

에라토스테네스의 체를 균일하게 만드는 몇 가지 방법이 있습니다. 더 빠르게:

• 더 효율적인 데이터 구조를 사용하세요. 2부터 n까지의 모든 숫자 목록은 비트 벡터와 같은 더 효율적인 데이터 구조에 저장될 수 있습니다. 이는 알고리즘의 공간 요구 사항을 줄이고 성능을 향상시킬 수 있습니다.
• 더 효율적인 표시 알고리즘을 사용하세요. 각 소수의 모든 배수를 표시하는 알고리즘을 더 효율적으로 만들 수 있습니다. 체 휠을 사용하여. 이렇게 하면 알고리즘의 시간 복잡도를 O(n)으로 줄일 수 있습니다.
• 알고리즘을 병렬화합니다. 알고리즘을 병렬화하여 최신 컴퓨터의 다중 코어를 활용할 수 있습니다. 이렇게 하면 알고리즘의 성능이 더욱 향상될 수 있습니다.

다음은 더 빠른 버전의 에라토스테네스의 체를 Python으로 구현한 것입니다.

import numpy as np

def sieve_of_eratosthenes_fast(n):
    """Return a list of all prime numbers below n."""

    # Create a bit vector to store the prime numbers.
    primes = np.ones(n // 2 + 1, dtype=np.bool)

    # Mark off all the multiples of 2.
    primes[3::2] = False

    # Iterate over the odd numbers from 3 to n.
    for i in range(3, int(n ** 0.5) + 1, 2):

        # If the number is prime, mark off all its multiples.
        if primes[i // 2]:
            primes[i * i // 2::i] = False

    # Return the list of prime numbers.
    return [2] + [2 * i + 1 for i in range(1, n // 2 + 1) if primes[i]]

이 알고리즘은 원래 버전보다 빠릅니다. 에라토스테네스의 체, 현대 컴퓨터에서는 약 0.01초 만에 100만 미만의 모든 소수를 찾아낼 수 있습니다. 컴퓨터.

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