限られた範囲内で素数を効率的にマッピングするにはどうすればよいでしょうか?

限られた範囲での効率的な素数マッピング

コンピューターサイエンスの分野では、特定の範囲内の素数を識別することは一般的なタスクです。目標は、数値を「素数である」ステータスに効率的にマッピングするデータ構造を作成することです。

1 つのアプローチは、ブール関数 isprime(n) を使用することです。ただし、メモリ消費を最適化するには、カスタム データ構造を使用することが望ましいです。範囲 (1, N] (N は定数) の場合、次の考慮事項が重要です。

エラトステネスのふるいのバリエーション

古典的なエラトステネスのふるいは次のようになります。ただし、このアプローチでも 5 の倍数には不要なビットが含まれます。

最適化アルゴリズム

によって提案されたより効率的なアルゴリズム。 AKS は、一般的な場合に最速の素数テストを提供します。ただし、限られた範囲で素数を見つけるには適していない可能性があります。

Python の実装

実用的な目的では、 Python 実装が利用可能です:

<code class="python">def isprime(n):
    if n == 2 or n == 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    w = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += w
        w = 6 - w
    return True</code>

このアルゴリズムは、素数 (2 と 3 以外) が 6k - 1 または 6k 1 のいずれかの形式であるという事実を利用します。これらの形式の約数のみを検索します。

追加オプション

速度向上のため、特に範囲が限られている場合には、フェルマーの定理に基づく擬似素数検定を使用できます。ただし、偽陽性 (カーマイケル数) を事前に計算します。 ) は、二分探索を活用することでさらに速度を向上させることができます。

以上が限られた範囲内で素数を効率的にマッピングするにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。