素数判定 Math.sqrt()

今回は paiza の「素数判定」の問題に挑戦！

📘 問題概要

• 整数 N が 1 つ与えられる
• N が素数かどうかを判定する問題
• 素数なら "YES"、素数でなければ "NO" を出力する
• 条件：1 ≤ N ≤ 10¹⁰

入力例:

2147483647

出力例:

YES

✅OK例：

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];

rl.on('line', line => lines.push(line));

rl.on('close', () => {
    const N = Number(lines[0]);
    
    let ans = 'YES';
    
    if (N === 1) {
        ans = 'NO';
    } else if (N % 2 === 0 && N !== 2) {
        // 偶数なら素数ではないのは確定（2以外）
        ans = 'NO';  
    } else if (N % 2 !== 0) { 
        // 奇数のときだけ割り算チェック
        for (let i = 3; i <= Math.floor(Math.sqrt(N)); i += 2) {
            if (N % i === 0) {
                ans = 'NO';
                break;
            }
        }
    }
    
    console.log(ans);
});

🔍 コードの流れ

• 標準入力から整数 N を受け取る
• 判定結果用の変数 ans を "YES" で初期化する
• N === 1 の場合
  • 1 は素数ではないため ans = "NO" にする
• N が 2 以外の偶数の場合
  • 偶数は素数ではないため ans = "NO" にする
• N が奇数の場合
  • 3 から √N まで、2 ずつ増やしながら割り算を試す
    ※ 2 以外の偶数はすべて除外済み → 割る必要があるのは「奇数」だけ
  • 割り切れる数が見つかったら
    • 素数ではないので ans = "NO"
    • それ以上のチェックをやめる
• すべての判定が終わったら ans を出力する

※ 補足

i <= Math.floor(Math.sqrt(N))

素数判定で見たいのは：「√N 以下の整数で割り切れるか？」

理由は👇
もし
N = a × b（a, b ≥ 2）
なら、どちらか一方は必ず √N 以下 になる。


つまり

• √N より大きい 数だけを調べても意味がない
• √N を超えた瞬間に探索をやめていい

🔍 √N が 整数でない場合

例：N = 10

√10 ≒ 3.16 → floor → 3

👉 3 まで調べれば十分（4 以上は不要）

🔍 √N が 整数の場合

例：N = 9

√9 = 3 → floor → 3

👉 3 をちゃんと調べる（重要！）

✨他のループ条件

for (let i = 3; i * i <= N; i += 2)

• Math.sqrt を毎回呼ばない
• 浮動小数点の誤差を避けられる
• 条件が数学的に直感的

📝まとめ

• 素数判定は √N まで調べれば十分
• 明らかに素数ではないケースは先に除外する
  • 1
  • 2 以外の偶数
• ループは 奇数だけでよい
• 無駄な計算を減らすことが高速化につながる