JavaScript の isPrime

1. JavaScript で数値が素数であるかどうかを確認するためのナイーブなソリューション
2. JavaScript で数値が素数であるかどうかを確認する平方根ソリューション

素数は、1 とそれ自体の 2つの要因で 1 よりも大きくなります。これは、素数が他の数で除算されるたびに常に余りを残すことを意味します。2つ以上の因子を持つ 1 より大きい他の数は、合成数と呼ばれます。

この記事では、JavaScript で数値が素数であるかどうかを確認するためのさまざまな方法について説明します。

JavaScript で数値が素数であるかどうかを確認するためのナイーブなソリューション

数 n が素数であるかどうかを確認する最も簡単な方法は、2 から n-1 まで反復してから、n がそれぞれで割り切れるかどうかを確認することです。

function isPrime(n) {
  if (n <= 1) return false;
  for (var i = 2; i <= n - 1; i++)
    if (n % i == 0) return false;
  return true;
}

console.log(isPrime(70));
console.log(isPrime(23));

時間計算量

2 から n-1 まで n-2 回繰り返します。このソリューションの時間計算量は O(n) です。

スペースの複雑さ

このソリューションのスペースの複雑さは O(1) です。

JavaScript で数値が素数であるかどうかを確認する平方根ソリューション

上記の解決策は、sqrt(n) まで繰り返すことで改善できます。これは、sqrt(n) * sqrt(n) = n という事実に基づいており、sqrt(n) よりも小さい係数が少なくとも 1つ存在する必要があります。[2, sqrt(n)] の範囲内の因子が見つからない場合、それは数値 n が素数であることを意味します。

function isPrime(n) {
  if (n <= 1) return false;
  for (var i = 2; i <= Math.sqrt(n); i++)
    if (n % i == 0) return false;
  return true;
}

console.log(isPrime(70));
console.log(isPrime(23));

時間計算量

最初の sqrt(n) の潜在的な要因を反復するため、上記のソリューションの時間計算量は sqrt(n) です。

スペースの複雑さ

このソリューションのスペースの複雑さは O(1) です。