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