基本情報技術者試験 - 令和5年公開問題(科目B) - 問1
問題
次のプログラム中の [ a ] と [ b ] に入れる正しい答えの組合せを,解答群の中から選べ。ここで,配列の要素番号は1から始まる。
関数 findPrimeNumbers は,引数で与えられた整数以下の,全ての素数だけを格納した配列を返す関数である。ここで,引数に与える整数は2以上である。
〔プログラム〕
解答群
関数 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
整数型の配列: 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 と等しくない |
正解と解説
正解設問1 ア
分野テクノロジ系 › 基礎理論 › アルゴリズムとプログラミング › プログラミング
解説
素数とは,1とその数自身以外では割り切れない,2以上の整数のことです。例えば,2,3,5,7は素数ですが,4は2で割り切れるので素数ではありません。このプログラムは,2から maxNum までの整数iを一つずつ取り出し,「iが素数かどうか」を調べて,素数なら配列pnListに追加します。
■ 空欄aの考え方
関数 findPrimeNumbers は,「引数で与えられた整数以下の」素数を全て返す関数です。「以下」なので maxNum 自身も調べる対象に含める必要があります。擬似言語の「iを2から maxNum まで1ずつ増やす」という書き方では,maxNum 自身も含めて繰り返します。そのため,空欄aは「maxNum」が正解です。「maxNum+1」にすると,maxNum より1大きい数まで調べてしまい,例えば maxNum が10のとき11も素数として配列に入ってしまいます。
■ 空欄bの考え方
内側の繰返しでは,iを2から「iの正の平方根の整数部分」までの数jで順に割ってみます。一つでも割り切れる数があれば,iは素数ではありません。「割り切れる」とは,割り算の余りが0になることです。そのため,空欄bは「i÷jの余りが0と等しい」が正解です。割り切れたら divideFlag を false にして,それ以上調べる必要がないので繰返しを終了します。
なお,平方根まで調べれば十分な理由は次のとおりです。例えば,36は「2×18」「3×12」「6×6」のように分解できますが,掛け合わせる二つの数のうち小さい方は必ず平方根の6以下になります。そのため,平方根以下の数で割り切れなければ,それより大きい数でも割り切れないと判断できます。