素数判定プログラムのトレース

■ 解き方の方針 外側のループで調べる整数の範囲と、内側のループで「素数ではない」と判定する条件を分けて考えます。 ■ 空欄a:調べる範囲 戻り値にはmaxNum以下の全ての素数を含める必要があります。maxNum自身が素数の場合も対象なので、iは2から maxNum まで調べます。maxNum + 1まで進めると、指定範囲外の値まで判定してしまいます。 ■ 空欄b:合成数を見つける条件 iがjで割り切れると、1とi以外の約数jをもつので、iは素数ではありません。割り切れる条件は i ÷ jの余りが0 です。このときdivideFlagをfalseにして内側のループを終了します。 ■ 平方根まで調べればよい理由 合成数iを$i = p \times q$と表したとき、pとqの両方が$\sqrt{i}$より大きいことはありません。したがって、iが合成数なら$\sqrt{i}$以下の約数が必ず見つかります。2や3では内側のループが実行されず、divideFlagがtrueのままなので正しく追加されます。 i jの範囲(2〜√iの整数部分) 割り切れるj pnListに追加 2 なし(√2≒1.4) − ○ 3 なし(√3≒1.7) − ○ 4 2 2 × 9 2〜3 3 × 11 2〜3 なし ○ ■ 正解と誤答の見分け方 したがって、正解は ア です。 商が1かどうかでは割り切れるかを判定できません。素数判定では余りが0かどうかを見ます。

次のプログラム中の  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
aの行から始まる繰返し処理を終了する
endif
endfor
if (divideFlag が true と等しい)
pnListの末尾にiの値を追加する
endif
endfor
return pnList

出典令和5年度 公開問題 基本情報技術者試験 科目B 問1
選択肢画像が未設定です