ゆめさくエンジニア研究所女性向けエンジニアスクール女性向けエンジニアスクール
ログイン

問1 平方根までの割り算で素数を集める

基本情報​技術者試験 令和5年度 公開問題 科目B、全6問のうちの問1。

出典：令和5年度 基本情報技術者試験 公開問題 科目B 問1（プログラムは原本の画像を文字に書き起こし、字下げは 1 段を空白 2 つで表した。空欄は［ a ］［ b ］で、解答群の表は 1 行の文に組み直した）

次のプログラム中の［ a ］と［ b ］に入れる正しい答えの組合せを，解答群の中から選べ。ここで，配列の要素番号は 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
  1. アa maxNum，b i ÷ j の余り が 0 と等しい
  2. イa maxNum，b i ÷ j の商 が 1 と等しくない
  3. ウa maxNum ＋ 1，b i ÷ j の余り が 0 と等しい
  4. エa maxNum ＋ 1，b i ÷ j の商 が 1 と等しくない
答えと解説を開く

正解はアです。

外側の繰返しは、素数かどうかを調べる候補 i を動かします。求めるのは引数の整数以下の素数なので、i は 2 から maxNum までです。maxNum ＋ 1 まで回すと、maxNum より大きい数まで調べてしまいます。内側の繰返しは、i を 2 から i の平方根の整数部分までの j で割ってみます。1 つでも割り切れる j があれば、i は素数ではありません。だから b は「i ÷ j の余りが 0 と等しい」で、そのとき divideFlag を false にして内側の繰返しを抜けます。maxNum ＝ 1⁠0 で追います。i ＝ 2 と 3 は平方根の整数部分が 1 なので内側を回らず、そのまま追加します。i ＝ 4 は j ＝ 2 で余り 0 なので外します。i ＝ 5 は j ＝ 2 で余り 1 なので追加します。i ＝ 6 は j ＝ 2 で外し、i ＝ 7 は j ＝ 2 で余り 1 なので追加します。i ＝ 8 は j ＝ 2 で外し、i ＝ 9 は j ＝ 2 で余り 1、j ＝ 3 で余り 0 なので外します。i ＝ 1⁠0 は j ＝ 2 で外します。pnList は {2, 3, 5, 7} になります。正解はアです。

ほかの選択肢が違う理由

  • イi が 4 以上なら、j ＝ 2 のときの商は 2 以上で、1 と等しくありません。4 以上の数が全部外れ、maxNum ＝ 1⁠0 なら {2, 3} しか返りません。
  • ウb は合っていますが、i を maxNum ＋ 1 まで回します。maxNum ＝ 1⁠0 なら 1⁠1 も調べて追加し、{2, 3, 5, 7, 1⁠1} になります。
  • エi を maxNum ＋ 1 まで回すうえに、商で判定するので 4 以上の数が全部外れます。maxNum ＝ 1⁠0 なら {2, 3} になります。

仕組み

ある数 i が 1 と自分以外で割り切れるなら、その割る数の片方は必ず i の平方根以下にあります。だから平方根まで試せば、素数かどうかが決まります。

「割り切れる」は「余りが 0」と同じ意味です。擬似言語では mod か「÷ の余り」で書きます。商で判定するのは、割り切れるかどうかを見る方法ではありません。

この問に出る言葉