与えられた範囲内で素数を効率的に見つけるにはどうすればよいでしょうか?

指定された範囲内の素数の検索

数学では、素数とは、1 とそれ自体を除く他の数で割り切れない 1 より大きい整数です。特定の範囲内で素数を見つけることは、一般的なプログラミング タスクとなる場合があります。 JavaScript でこの問題にアプローチする方法の詳細な説明は次のとおりです。

ブルート フォース アプローチ

提供されたコード スニペットは、ブルート フォース アプローチを使用して 0 から 100 までの素数を見つけようとします。数値が 2 から 12 までの数値で割り切れるかどうかを確認し、約数が見つからない場合はその数値を返します。ただし、このアプローチにはいくつかの欠点があります。

• 特に大きな範囲の場合、非効率的です。
• より大きな範囲の素数を見つけるために拡張するのは困難です。

エラトステネスのふるい

素数を見つけるためのより効率的なアルゴリズムはと呼ばれますエラトステネスのふるい。その仕組みは次のとおりです。

1. 長さが最大 ​​1 の sieve という配列を作成します。
2. 配列内のすべての要素を false に初期化します (false は数値が素数であることを意味すると仮定します)。
3. 2 から の平方根まで sieve 配列を反復処理します。 max.
4. 各素数 i について、i j から max. j] を true に設定することで、その倍数をすべて非素数としてマークします。 🎜>反復の後、sieve 配列内のマークされていない数値は素数になります。

JavaScript では、エラトステネスのふるいのコードは次のようになります。

<code class="js">function getPrimes(max) {
    var sieve = [], i, j, primes = [];
    for (i = 2; i <= max; ++i) {
        if (!sieve[i]) {
            // i has not been marked -- it is prime
            primes.push(i);
            for (j = i << 1; j <= max; j += i) {
                sieve[j] = true;
            }
        }
    }
    return primes;
}</code>

このアプローチの時間計算量は O(n log log n) であり、総当たりアプローチよりもはるかに効率的です。

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