こんにちは！
今回は「Javascriptで素数かどうかを判定するロジック」についてお伝えしたいと思います。
最近、アルゴリズムの勉強をしておりまして、素数を判定するロジックを作成したので共有いたします。
素数はRSA暗号で使われたりと、意外と身近に使われてるようですね。
まず、素数とは？（分かってるという方は飛ばしてください〜）
wikipediaは以下のように定義されてました。
素数（そすう、英: primeあるいはprime number）とは、2 以上の自然数で、正の約数が 1 と自分自身のみであるもののことである。正の約数の個数が 2 である自然数と言い換えることもできる。1 より大きい自然数で素数でないものは合成数と呼ばれる。
参考：wikipedia
Javascriptで素数かどうかを判定するロジック
素数を算出するポイント
ポイント
合成数（1 より大きい自然数で素数でないもの）でないことを確かめる
合成数は2以上√N以下までの数で割り切れる
実際の素数判定のアルゴリズムを以下に示します。
// 素数かどうかを判定する
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とする点になります。
以上、お疲れさまでした〜🍵