範囲内の素数を数える JavaScript プログラム

#素数とは、完全な約数が 2 つだけある数です。指定された範囲内の素数の数を見つける 2 つの方法を見ていきます。 1 つ目は、総当たりの方法を使用する方法ですが、これは時間の複雑さが多少高くなります。次に、この方法を改良し、エラトステネスのふるいアルゴリズムを採用して、時間計算量を改善します。この記事では、JavaScript プログラミング言語を使用して、指定された範囲内の素数の総数を求めます。

暴力法

まず、このメソッドでは、数値が素数かどうかを調べる方法を学びます。それは 2 つの方法で見つけることができます。 1 つのメソッドの時間計算量は O(N) で、もう 1 つのメソッドの時間計算量は O(sqrt(N)) です。

数値が素数かどうかを判断する直接的な方法

＃＃＃例＃＃＃

まず、数値が得られるまで for ループを実行し、その数値を割り切れる数を数えます。割り切れる数が 2 に等しくない場合、その数値は素数ではありません。それ以外の場合、number は素数になります。コードを見てみましょう -

リーリー

上記のコードでは、1 から数値までを走査し、指定された数値を除算できる数値範囲内の数値を見つけ、指定された数値を除算できる数値の数を取得し、これに基づいて結果を出力します。

上記のコードの時間計算量は O(N) で、各数値が素数かどうかを確認するには O(N*N) のコストがかかります。つまり、これは良い確認方法ではありません。

数学的方法

ある数値が別の数値を完全に割るとき、商も完全な整数になることがわかっています。つまり、数値 p を数値 q で割ることができる場合、商は r、つまり q * r = p になります。 。 r はまた、数値 p を商 q で割ります。つまり、完全な約数は常にペアで存在することになります。

＃＃＃例＃＃＃

上記の議論から、N の平方根への除算を確認するだけであれば、非常に短時間で同じ結果が得られると結論付けることができます。上記のメソッドのコードを見てみましょう -

リーリー

上記のコードでは、for ループのスコープを変更して前のコードを変更しただけです。これは、N 要素の最初の平方根のみをチェックし、カウントを 2 増やしたからです。

上記のコードの時間計算量は O(sqrt(N)) であり、これより優れています。つまり、このメソッドを使用して、指定された範囲内に存在する素数の数を見つけることができます。

L から R までの範囲内の素数の数

＃＃＃例＃＃＃

前に指定したコードを範囲内に実装し、指定された範囲内の素数の数を数えます。コードを実装しましょう -

リーリー

上記のコードでは、for ループを使用して L から R までの範囲を反復し、各反復で現在の数値が素数かどうかを確認します。数値が素数の場合、カウントをインクリメントし、最後に値を出力します。

上記のコードの時間計算量は O(N*N) です。ここで、N は Range の要素の数です。

エラトステネスアルゴリズムスクリーニング

＃＃＃例＃＃＃

エラトステネスのふるいアルゴリズムは非常に効率的で、指定された範囲内の素数の数を O(Nlog(log(N))) 時間で見つけることができます。他のアルゴリズムと比較して、非常に高速です。ふるいは O(N) スペースを占有しますが、時間は非常に効率的であるため、それは問題ではありません。コードを見てから、コードの説明に進みます -

リーリー

上記のコードでは、エラトステネスのふるいの実装が見られます。最初にサイズ R を含む配列を作成し、その後 for ループを使用して配列を反復処理します。反復ごとに、現在の数値が 1 でない場合、それは素数ではないことを意味し、それ以外の場合は素数であり、R より小さいすべての数値が得られます。現在の素数の倍数は削除されます。次に、0 から現在のインデックスまでの素数カウントを格納するプレフィックス配列を作成し、0 から R までの範囲のすべてのクエリに定数時間で回答を提供します。

時間と空間の複雑さ

上記のコードの時間計算量は O(N*log(log(N))) で、O(N*N) や O(N*(sqrt(N))) に比べてはるかに優れています。前のコードと比較して、上記のコードの空間複雑度は O(N) です。

＃＃＃結論は＃＃＃

このチュートリアルでは、JavaScript プログラミング言語を使用して、指定された範囲内の素数の数を見つける方法を学びました。素数とは、完全な約数がちょうど 2 つある数です。 1 は完全約数が 1 つしかないため、素数ではありません。時間計算量が O(N*N)、O(N*sqrt(N))、O(N*log(log(N))) の 3 つの方法を見てきました。さらに、最初の 2 つの方法の空間計算量は O(1) で、エラトステネスのふるい法の空間計算量は O(N) です。

以上が範囲内の素数を数える JavaScript プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。