令和5年度 公開問題 科目B 問1
次のプログラム中の[ ]と[ ]に入れる正しい答えの組合せを,解答群の中から選べ。ここで,配列の要素番号は 1 から始まる。
関数 findPrimeNumbers は,引数で与えられた整数以下の,全ての素数だけを格納した配列を返す関数である。ここで,引数に与える整数は 2 以上である。
○整数型の配列: findPrimeNumbers(整数型: maxNum)
整数型の配列: pnList ← {} // 要素数0の配列
整数型: i, j
論理型: divideFlag
for (i を 2 から [ a ] まで 1 ずつ増やす)
divideFlag ← true
/* iの正の平方根の整数部分が2未満のときは,繰返し処理を実行しない */
for (j を 2 から iの正の平方根の整数部分 まで 1 ずつ増やす) // α
if ([ b ])
divideFlag ← false
αの行から始まる繰返し処理を終了する
endif
endfor
if (divideFlag が true と等しい)
pnListの末尾 に iの値 を追加する
endif
endfor
return pnList
| a | b | |
|---|---|---|
| ア | maxNum | i ÷ j の余り が 0 と等しい |
| イ | maxNum | i ÷ j の商 が 1 と等しくない |
| ウ | maxNum + 1 | i ÷ j の余り が 0 と等しい |
| エ | maxNum + 1 | i ÷ j の商 が 1 と等しくない |
出典:令和5年度 基本情報技術者試験 科目B 公開問題 問1
正解と解説を見る
正解:ア
ポイント:素数判定は「2 から √i までのどれかで割り切れるか」。割り切れる=余りが 0。
maxNum 以下の素数を全部求める関数です。外側のループで 2 から maxNum までの各 i を調べます。疑似言語の「i を 2 から maxNum まで」は maxNum を含むので、空欄aは maxNum。maxNum + 1 にすると、maxNum より大きい数まで調べてしまいます(例:maxNum=10 で 11 が入る)。
内側のループは、i を 2 から √i(の整数部分)までの数 j で割ってみます。一度でも割り切れれば素数ではないので、divideFlag を false にして内側のループを抜けます。割り切れるとは「i ÷ j の余りが 0」なので、空欄bは「i ÷ j の余り が 0 と等しい」。
よって(ア)。
イ・エ:「商が 1 と等しくない」は割り切れるかどうかと関係がありません。例えば i=5, j=2 なら商は 2 なので、素数の 5 を素数でないと判定してしまいます。
√i までで十分な理由:i=a×b と分解できるなら、a と b の小さい方は必ず √i 以下だからです。
解説と下の表はこのサイトが作成したものです(表は、正解の選択肢を入れたプログラムを実際に実行した結果です)。
正解のプログラムを動かしてみる
findPrimeNumbers(6) を呼び出したときに、1行ずつ何が起きるかの表です(全部で 37 手)。「真・偽」は、その行の条件の判定です。
| 手 | 実行した行 | 変わった値 |
|---|---|---|
| 1 | 1行目○整数型の配列: findPrimeNumbers(整数型: maxNum) | maxNum = 6 |
| 2 | 2行目整数型の配列: pnList ← {} // 要素数0の配列 | pnList = {} |
| 3 | 3行目整数型: i, j | |
| 4 | 4行目論理型: divideFlag | |
| 5 | 5行目for (i を 2 から maxNum まで 1 ずつ増やす) | 真 i = 2 |
| 6 | 6行目divideFlag ← true | divideFlag = true |
| 7 | 8行目for (j を 2 から iの正の平方根の整数部分 まで 1 ずつ増やす) // α | 偽 j = 2 |
| 8 | 14行目if (divideFlag が true と等しい) | 真 |
| 9 | 15行目pnListの末尾 に iの値 を追加する | pnList = {2} |
| 10 | 5行目for (i を 2 から maxNum まで 1 ずつ増やす) | 真 i = 3 |
| 11 | 6行目divideFlag ← true | |
| 12 | 8行目for (j を 2 から iの正の平方根の整数部分 まで 1 ずつ増やす) // α | 偽 |
| 13 | 14行目if (divideFlag が true と等しい) | 真 |
| 14 | 15行目pnListの末尾 に iの値 を追加する | pnList = {2, 3} |
| 15 | 5行目for (i を 2 から maxNum まで 1 ずつ増やす) | 真 i = 4 |
| 16 | 6行目divideFlag ← true | |
| 17 | 8行目for (j を 2 から iの正の平方根の整数部分 まで 1 ずつ増やす) // α | 真 |
| 18 | 9行目if (i ÷ j の余り が 0 と等しい) | 真 |
| 19 | 10行目divideFlag ← false | divideFlag = false |
| 20 | 11行目αの行から始まる繰返し処理を終了する | |
| 21 | 14行目if (divideFlag が true と等しい) | 偽 |
| 22 | 5行目for (i を 2 から maxNum まで 1 ずつ増やす) | 真 i = 5 |
| 23 | 6行目divideFlag ← true | divideFlag = true |
| 24 | 8行目for (j を 2 から iの正の平方根の整数部分 まで 1 ずつ増やす) // α | 真 |
| 25 | 9行目if (i ÷ j の余り が 0 と等しい) | 偽 |
| 26 | 8行目for (j を 2 から iの正の平方根の整数部分 まで 1 ずつ増やす) // α | 偽 j = 3 |
| 27 | 14行目if (divideFlag が true と等しい) | 真 |
| 28 | 15行目pnListの末尾 に iの値 を追加する | pnList = {2, 3, 5} |
| 29 | 5行目for (i を 2 から maxNum まで 1 ずつ増やす) | 真 i = 6 |
| 30 | 6行目divideFlag ← true | |
| 31 | 8行目for (j を 2 から iの正の平方根の整数部分 まで 1 ずつ増やす) // α | 真 j = 2 |
| 32 | 9行目if (i ÷ j の余り が 0 と等しい) | 真 |
| 33 | 10行目divideFlag ← false | divideFlag = false |
| 34 | 11行目αの行から始まる繰返し処理を終了する | |
| 35 | 14行目if (divideFlag が true と等しい) | 偽 |
| 36 | 5行目for (i を 2 から maxNum まで 1 ずつ増やす) | 偽 i = 7 |
| 37 | 18行目return pnList |
戻り値:{2, 3, 5}