JavaScriptで素数を判断する方法

PHPz
PHPzオリジナル
2023-04-24 10:51:241163ブラウズ

素数とは、1 とそれ自体以外に因数を持たない 2 以上の自然数を指します。素数は暗号学、コンピューター サイエンス、その他の分野で広く使用されているため、入力が素数かどうかを判断できる JavaScript プログラムを実装すると非常に便利です。

JavaScript では、ループと条件ステートメントを使用して素数を決定できます。基本的な考え方は、入力された数値を1つずつ判定し、1と自分自身以外の因数があれば素数ではなく、なければ素数です。

以下は、素数を実装するための簡単な JavaScript プログラムです:

function isPrime(num){
  if(num <= 1){   // 1不是素数
    return false;
  }
  for(var i = 2; i < num; i++){  // 从2到num-1逐个判断
    if(num % i == 0){  // 如果可以整除,说明不是素数
      return false;
    }
  }
  return true;  // 如果没有被整除,则是素数
}

このプログラムでは、まず入力数値が 1 以下かどうかを判断します。そうであれば、そうではありません。素数。次に、for ループを使用して、2 から 1 つずつ割り切れるかどうかを判断します。割り切れる場合は素数ではないことを意味し、直接 false を返します。割り切れない場合は素数であることを意味し、true を返します。

このプログラムの時間計算量は O(n) ですが、大きな数値を判断する場合には非常に時間がかかる可能性があるため、いくつかの最適化アルゴリズムを使用して効率を向上させることができます。

一般的な最適化アルゴリズムの 1 つは、入力数値の平方根以下の数値のみを決定するものです。数値 n が素数ではない場合、数値 n は 2 つの因数 a と b に分解され、少なくとも 1 つの因数がその平方根以下であるためです。したがって、入力数値の平方根以下の数値が割り切れるかどうかを判断するだけで済みます。

以下は、最適化された JavaScript 素数判定プログラムです。

function isPrime(num){
  if(num <= 1){
    return false;
  }
  for(var i = 2; i <= Math.sqrt(num); i++){  // 只判断小于等于平方根的数
    if(num % i == 0){
      return false;
    }
  }
  return true;
}

このプログラムの時間計算量は O(√n) で、前のプログラムよりもはるかに効率的です。

実際のアプリケーションでは、エラトステネスふるい法やオイラーふるい法など、より高度なアルゴリズムを使用して素数を決定することもできます。これらのアルゴリズムは、範囲内の素数を計算するために使用でき、その時間計算量は通常、線形または線形対数レベルであるため、大規模な素数計算に非常に適しています。

つまり、JavaScript を使用して素数判定を実装すると、素数の概念と応用をより深く理解し、プログラミングのレベルを向上させることができます。

以上がJavaScriptで素数を判断する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。