ITパスポート 2026年 問85

素数判定アルゴリズム【ITパスポート解説】

正解の理由

• divを2で初期化し、2から順に割り算していく（割り切れれば素数でない）。
• 割り切れる数が見つからなければ素数と判定する。

解法ステップ

1. 素数の定義を確認する：1より大きく、自分自身と1以外に約数がない整数。
2. 早期判定（if節）で2未満の数を弾く：
   • 0や1は素数でないのでfalseを返すべき。
   • 2は素数なのでここで弾かない（ifがfalseである必要がある）。
3. ループで2から順に割り算を試す（divを2から始めて、num-1まで試す）：
   • もし余りが0（$num\mathrm{mod}div=0$）なら合成数（素数でない）だからfalse。
   • 最後まで割り切れるものがなければtrue（素数）。
4. 条件を満たす文字列を当てはめる：a = 「より小さい」、b = 「より大きい」。

選択肢別の誤答解説

• ア（a: 以下、b: と等しい）
  aが「以下（≤）」だとnum = 2のときifが真になり、2のときfalseを返してしまいます。これは問題文の「isPrime(2) の戻り値がtrue」と矛盾します。bが「と等しい（=）」だとwhileがほとんど実行されず、正しく判定できません。
• イ（a: 以下、b: より大きい）
  aの「以下（≤）」が誤りのため不適。num = 2のとき誤ってfalseを返します。
• ウ（a: より小さい、b: と等しい）
  aは正しい（2未満を弾く）が、bが「と等しい」だとwhile (num == div) の意味になり、通常ループが実行されず正しい判定ができません（divは2で固定され、numが2のときのみ真になります）。
• エ（a: より小さい、b: より大きい）
  aが「numが2より小さいときfalse」を意味し1や0を弾けます。bが「numがdivより大きい（num > div）」であればdivが2からnum-1まで回り、約数を正しく検査できます。したがって処理が意図通りになります（正解）。

よくある誤解

• 「2を特別扱いするのは不要」
  2は最小の素数なので、特にifで2を弾いてしまうと誤判定になります。2は素数として残す必要があります。
• 「ループ条件を <= にすれば良い」と思うミス
  div ≤ numとするとdiv = numのときも調べてしまい、必ず最後にnum % num == 0となり誤って合成数扱い（false）になるのでダメです。
• 「divを2以外から始めると早く判定できる」と考える誤り
  例えば奇数だけ調べる高速化は可能ですが、その前に2の扱い（偶数かどうか）を別に処理するなど注意が必要です。

補足コラム

• divを2からnum-1まで調べると計算量は $O(num)$ で大きな数に不向きです。改善策としてdivの上限を $\sqrt{num}$（numの平方根）にすれば十分です。理由は、もしnum = a × bと分解できるなら、どちらか一方は $\le \sqrt{num}$ だからです。
  具体的なループ条件は「div × div ≤ num（またはdiv ≤ √num）」にすればよいです。
• さらに速くするにはエラトステネスの篩（ふるい）や確率的素数判定（ミラー–ラビンなど）がありますが、初学者はまず基本的な割り算ループの考え方を押さえましょう。

def isPrime(num: int) -> bool:
    if num < 2:          # 2 より小さい -> 素数ではない
        return False
    div = 2
    while num > div:     # div が num より小さい間（2..num-1）を調べる
        if num % div == 0:
            return False
        div += 1
    return True

FAQ