JavaScript で数値が素数かどうかを効率的に判断するにはどうすればよいですか?

JavaScript での素数チェック

この記事では、JavaScript を使用せずに指定された数値が素数であるかどうかを判断する問題について説明します。素数とは、1 より大きく、1 とそれ自体を除く他の自然数では割り切れない整数です。

解決策 1

従来の方法では、2 から反復する必要があります。入力数値の平方根を計算し、その数値がこれらのいずれかで割り切れるかどうかを確認します。もしそうであれば、それはプライムではありません。それ以外の場合は、そうです。

<code class="javascript">let inputValue = 7;
let isPrime = inputValue == 1 ? false : true; // because 1 is not prime

for (let i = 2; i < inputValue; i++) {
  inputValue % i == 0 ? (isPrime *= false) : (isPrime *= true);
}

alert(`${inputValue} is ${isPrime ? 'prime' : 'not prime'} number`);

時間計算量: O(sqrt(n))
空間計算量: O(1)

解決策 2

別のアプローチでは、2 より大きい素数は奇数になり得ないという事実を利用します。したがって、2 で割り切れる可能性をチェックし、次に入力数値の平方根までの奇数で割り切れるかどうかをチェックするだけで十分です。この最適化により、実行時間が大幅に短縮されます。

<code class="javascript">const isPrime = num => {
  if (num <= 1) return false;
  if (num <= 3) return true;
  if (num % 2 == 0 || num % 3 == 0) return false;
  for (let i = 5; i * i <= num; i += 6) {
    if (num % i == 0 || num % (i + 2) == 0) return false;
  }
  return true;
};</code>

時間計算量: O(sqrt(n))
空間計算量: O(1)

以上がJavaScript で数値が素数かどうかを効率的に判断するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。