擬似言語の素数判定プログラム、境界の値をどう見極めるか
ITパスポート試験 令和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：と等しい
- イ
a：以下、b：より大きい
- ウ
a：より小さい、b：と等しい
- エ
a：より小さい、b：より大きい
会話形式の解説
講師この問題は、素数かどうかを判定するプログラムの穴埋めです。注目点は二つあります。最初のif文で除外すべき数はどれか、そしてwhileの繰返しをどこまで続けるか、です。問題文にある「isPrime(2)はtrue」という例が大きな手がかりになります。
受験者素数は1と自分自身でしか割り切れない数ですよね。aは「2以下ならfalse」にすればよい気がしたのですが、それだと2も除外されてしまいますか。
講師そのとおりです。aに「以下」を入れると、num=2のときに「2が2以下」が成り立ち、falseが返ります。問題文ではisPrime(2)はtrueなので、矛盾します。素数は1より大きい整数なので、ここで除外したいのは2未満、つまり1だけです。
受験者では、aは「より小さい」ですね。「以下」が入っている組合せは、bが何であっても誤りになるということですか。
講師はい。aが「以下」の組合せは、bに正しい条件が入っていても2をfalseにしてしまうので不適切です。次はbです。whileの括弧の中は、繰返しを「続ける」条件である点に注意してください。終わる条件ではありません。
受験者divは2から1ずつ増えていきます。割り切れるかを調べたいのは、2からnum-1までの数ということでしょうか。
講師そうです。divがnumに達したところで止める必要があります。止めないと、num÷numの余りは必ず0なので、素数でもfalseになってしまいます。ですから、続ける条件は「numがdivより大きい」です。
受験者bを「と等しい」にした場合はどうなりますか。numとdivが等しいときだけ繰り返す、という意味になりそうです。
講師その読み方で合っています。num=2だとdivも2なのでループに入り、2÷2の余りが0でfalseが返ります。逆に3以上の数ではdiv=2と等しくないのでループに入らず、そのままtrueになります。つまり、4のような素数でない数でもtrueになってしまいます。
受験者aが「より小さい」、bが「より大きい」の組合せで、具体的な数を入れて確かめてみます。num=2なら、2は2より小さくないのでelseに進み、「2が2より大きい」が成り立たないのでループに入らず、trueになります。
講師問題文の例と一致しましたね。num=5も見てみましょう。divが2、3、4のときの余りはそれぞれ1、2、1で、どれも0ではありません。divが5になると「5が5より大きい」が成り立たないのでループを抜け、trueが返ります。
受験者num=4なら、div=2で余りが0になってfalseですね。1は最初のif文でfalseになります。どの数でも正しく判定できるので、この組合せが正解だと納得できました。
講師よくできました。この種の穴埋めでは、「以下」と「より小さい」のように、境界の値を含むかどうかだけが違う選択肢がよく出ます。迷ったら境界の値、今回なら2を実際に代入してみてください。問題文に示された例は、その確認にそのまま使えます。
まとめ
素数は1より大きく、1と自分自身以外に約数を持たない整数なので、最初のif文では2未満の数だけをfalseにする必要があり、aは「より小さい」が入ります。whileの括弧内は繰返しを続ける条件で、divを2からnum-1まで動かし、numに達したら止めるため、bは「より大きい」が入ります。aを「以下」にすると素数である2がfalseになり、bを「と等しい」にすると約数を順に調べられません。num=2、4、5を代入してトレースすると、この組合せで正しく判定できることを確かめられます。
解答・解説
正解はエです
この問題のテーマ
素数を判定する関数isPrimeの擬似言語プログラムで、2未満の数を除外する条件（a）と、割り切れるかを調べ続ける繰返しの継続条件（b）を穴埋めする問題です。
解き方の考え方
素数は1より大きく、1と自分自身以外に約数を持たない整数です。そのため、aの条件では2未満の数だけをfalseにし、2は素数として残す必要があります。bはwhileの継続条件なので、divを2からnum-1まで動かし、divがnumに達したところで止まる条件を選びます。最後に、num=2、4、5などの具体的な値をトレースして確かめると確実です。
選択肢ごとの解説
- ×ア a：以下、b：と等しいaの「以下」を入れると、num=2のときに「2が2以下」が成り立ってfalseが返ります。isPrime(2)はtrueという問題文の条件に反します。また、bの「と等しい」では、numとdivが等しいときしか繰り返さないので、約数を順に調べることができません。
- ×イ a：以下、b：より大きいbの「より大きい」は正しい継続条件です。しかし、aが「以下」のため、num=2が最初のif文でfalseになってしまいます。素数である2を素数でないと判定するので不適切です。
- ×ウ a：より小さい、b：と等しいaの「より小さい」は正しい条件です。しかし、bが「と等しい」だと、num=2のときは2÷2の余りが0になってfalseが返ります。3以上の数ではdiv=2と等しくないためループに入らず、4のような合成数でもtrueになってしまいます。
- ○エ a：より小さい、b：より大きいaの「より小さい」により、2未満の数（1）だけがfalseになり、2は次の処理へ進みます。bの「より大きい」により、divは2からnum-1まで動いて割り切れるかが調べられ、約数がなければループを抜けてtrueが返ります。num=2ではループに入らずtrueになり、問題文の例とも一致します。
補足
エの組合せでトレースしてみます。num=5では、divが2、3、4のときの余りはそれぞれ1、2、1です。divが5になると「5が5より大きい」が成り立たないのでループを抜け、trueが返ります。num=4では、div=2で余りが0になりfalseが返ります。穴埋め問題では、「以下」と「より小さい」のように境界の値を含むかどうかだけが違う選択肢がよく出るので、境界の値を実際に代入して確かめる習慣をつけておきましょう。
POINT
- 素数は1より大きく、1と自分自身以外に約数を持たない整数なので、1は素数ではありません。
- whileの括弧内は「繰り返しを続ける条件」であり、終了条件ではない点に注意します。
- 約数の検査はdiv=2からnum-1までが対象で、divがnumに達したら止めないと、num÷numの余りが0になってfalseになります。
- 問題文に示された例（isPrime(2)がtrue）は、境界条件を判断する大きな手がかりになります。