素数判定アルゴリズムの条件式｜ITパスポート 令和8年 公開問題 問85
出典：令和8年 公開問題 問85
分野：基礎理論（大分類） ／ アルゴリズムとプログラミング
関数 isPrime は，引数として与えられた正の整数が，素数であれば true を，素数でなければ false を戻り値とする。例えば，関数 isPrime を isPrime(2)として呼び出したときの戻り値は true である。プログラム中の a，b に入れる字句の適切な組合せはどれか。
［プログラム］
○論理型：isPrime(整数型：num)
整数型：div ← 2
if (num が 2 ［a］)
return false
else
while (num が div ［b］)
if (num ÷ div の余り が 0 と等しい)
return false
else
div ← div + 1
endif
endwhile
return true
endif
| a | b | |
|---|---|---|
| ア | 以下 | と等しい |
| イ | 以下 | より大きい |
| ウ | より小さい | と等しい |
| エ | より小さい | より大きい |
TSUNAGARU-ADVICE
まず押さえたいこと
素数判定は、整数が約数として割り切れないか調べるアルゴリズムを理解することから始めます。特に判定範囲の指定と端点条件の扱いを正しく設定することが重要です。
迷ったときの判断軸
判定ループの範囲は、2以上 num未満の数で割り切れるかを調べるため、きちんと「より小さい」「より大きい」の関係を見極めましょう。等しいや以下を用いると判定漏れや誤判定の原因となりやすいです。
次の学習につなげるために
判定範囲の最適化や効率的な素数判定（例えば、sqrt(num)までの検査）に進む前段階として、この問題の理解で基本的な境界条件を身につけることが大切です。
素数判定とは、2以上の整数が1と自分自身以外に約数を持たないことを確かめる処理です。関数 isPrime は与えられた整数 num が素数なら true、そうでなければ false を返します。
このプログラムのポイントは、判定処理の繰り返し範囲と境界条件の設定です。
まず、2 以下の数値は素数の定義上、2 は素数なので除外せず処理します。1 やそれ未満は素数ではないため false を返す条件が必要です。従って「if (num が 2 より小さい)」の判定で false を返します。
次に割り切れるかの検査は約数を 2 から num-1 まで順に調べるのが基本ですが、効率向上のために num より小さい数(div < num)までで判定します。条件式が「num が div より大きい」で繰り返すループが正しい範囲を示します。
したがって、条件式 a は「より小さい」、条件式 b は「より大きい」が適切です。
したがって、エが適切です。
❌他選択肢が誤りの理由
ア：a＝以下、b＝と等しい
⇒「以下」は num=2 の場合に誤判定が起こる可能性があり、またループの終端条件も不適切です。
イ：a＝以下、b＝より大きい
⇒「以下」で 2 以下を一律に除外しているため、2 が素数である処理に誤りを生みます。
ウ：a＝より小さい、b＝と等しい
⇒ループ条件が「と等しい」は割り算の検査範囲が狭まり判定漏れになります。