素数生成を高速化するためにエラトステネスのふるいアルゴリズムを最適化するにはどうすればよいでしょうか?

エラトステネスのふるい

エラトステネスのふるいは古代のアルゴリズムですが、指定された数以下のすべての素数を見つけるための簡単で効率的な方法として今日でも使用されています。 。このアルゴリズムは、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]

このアルゴリズムは実装が比較的簡単です。そしてそれは非常に効率的です。たとえば、現代のコンピューターでは、100 万以下のすべての素数を約 0.1 秒で見つけることができます。

時間計算量

エラトステネスの篩の時間計算量は 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]]

このアルゴリズムは、元のバージョンよりも高速ですエラトステネスのふるいの100万未満のすべての素数を現代のコンピュータでは約0.01秒で見つけることができます。コンピューター

以上が素数生成を高速化するためにエラトステネスのふるいアルゴリズムを最適化するにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。