うごく基本情報

令和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
ab
アmaxNumi ÷ j の余り が 0 と等しい
イmaxNumi ÷ j の商 が 1 と等しくない
ウmaxNum + 1i ÷ j の余り が 0 と等しい
エmaxNum + 1i ÷ 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 手)。「真・偽」は、その行の条件の判定です。

手実行した行変わった値
11行目○整数型の配列: findPrimeNumbers(整数型: maxNum)maxNum = 6
22行目整数型の配列: pnList ← {} // 要素数0の配列pnList = {}
33行目整数型: i, j
44行目論理型: divideFlag
55行目for (i を 2 から maxNum まで 1 ずつ増やす)真
i = 2
66行目divideFlag ← truedivideFlag = true
78行目for (j を 2 から iの正の平方根の整数部分 まで 1 ずつ増やす) // α偽
j = 2
814行目if (divideFlag が true と等しい)真
915行目pnListの末尾 に iの値 を追加するpnList = {2}
105行目for (i を 2 から maxNum まで 1 ずつ増やす)真
i = 3
116行目divideFlag ← true
128行目for (j を 2 から iの正の平方根の整数部分 まで 1 ずつ増やす) // α偽
1314行目if (divideFlag が true と等しい)真
1415行目pnListの末尾 に iの値 を追加するpnList = {2, 3}
155行目for (i を 2 から maxNum まで 1 ずつ増やす)真
i = 4
166行目divideFlag ← true
178行目for (j を 2 から iの正の平方根の整数部分 まで 1 ずつ増やす) // α真
189行目if (i ÷ j の余り が 0 と等しい)真
1910行目divideFlag ← falsedivideFlag = false
2011行目αの行から始まる繰返し処理を終了する
2114行目if (divideFlag が true と等しい)偽
225行目for (i を 2 から maxNum まで 1 ずつ増やす)真
i = 5
236行目divideFlag ← truedivideFlag = true
248行目for (j を 2 から iの正の平方根の整数部分 まで 1 ずつ増やす) // α真
259行目if (i ÷ j の余り が 0 と等しい)偽
268行目for (j を 2 から iの正の平方根の整数部分 まで 1 ずつ増やす) // α偽
j = 3
2714行目if (divideFlag が true と等しい)真
2815行目pnListの末尾 に iの値 を追加するpnList = {2, 3, 5}
295行目for (i を 2 から maxNum まで 1 ずつ増やす)真
i = 6
306行目divideFlag ← true
318行目for (j を 2 から iの正の平方根の整数部分 まで 1 ずつ増やす) // α真
j = 2
329行目if (i ÷ j の余り が 0 と等しい)真
3310行目divideFlag ← falsedivideFlag = false
3411行目αの行から始まる繰返し処理を終了する
3514行目if (divideFlag が true と等しい)偽
365行目for (i を 2 から maxNum まで 1 ずつ増やす)偽
i = 7
3718行目return pnList

戻り値:{2, 3, 5}

サイトで、1行ずつ予想しながら動かす →