【Javascript】素数かどうかを判定するロジック

こんにちは！

今回は「Javascriptで素数かどうかを判定するロジック」についてお伝えしたいと思います。

最近、アルゴリズムの勉強をしておりまして、素数を判定するロジックを作成したので共有いたします。

素数はRSA暗号で使われたりと、意外と身近に使われてるようですね。

まず、素数とは？（分かってるという方は飛ばしてください〜）

wikipediaは以下のように定義されてました。

素数（そすう、英: primeあるいはprime number）とは、2 以上の自然数で、正の約数が 1 と自分自身のみであるもののことである。正の約数の個数が 2 である自然数と言い換えることもできる。1 より大きい自然数で素数でないものは合成数と呼ばれる。

参考：wikipedia

Javascriptで素数かどうかを判定するロジック

素数を算出するポイント

実際の素数判定のアルゴリズムを以下に示します。

// 素数かどうかを判定する
const isPrime = (n) => {
  for (let i=2; i*i<=n; i++) { // iは2〜√nまで+1ずつ変化
    if (n % i === 0) return false;
  }
  return true;
};
console.log(isPrime(4)) // false
console.log(isPrime(5)) // true
console.log(isPrime(137)) // true

これで最小の計算量で素数かどうかを判定することができました。
ポイントはfor文の終了をnではなく、√nとする点になります。

以上、お疲れさまでした〜🍵