素数を求める処理【基本情報技術者試験 科目B 公開問題】

← 科目Bの公開問題一覧へ戻る

　基本情報技術者試験の科目Bの公開問題を題材に，素数を求める処理について学習します。この問題では，割り算の余りや平方根を利用して，整数が素数かどうかを判定する方法を確認します。

令和5年度 基本情報技術者試験 公開問題 科目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

解答群

	a	b
ア	maxNum	i ÷ j の余り が 0 と等しい
イ	maxNum	i ÷ j の商 が 1 と等しくない
ウ	maxNum ＋ 1	i ÷ j の余り が 0 と等しい
エ	maxNum ＋ 1	i ÷ j の商 が 1 と等しくない

【参考】	「流れ図と擬似言語によるプログラミングの基礎まとめ」 「アルゴリズムと計算量の基礎まとめ」

この問題のポイント

　この問題から学べることは，

• 素数を判定する方法
• 割り算の余りを利用して，整数が割り切れるかを判定する方法
• 整数の平方根まで調べて，素数かどうかを判定する方法
• 繰返し処理と条件分岐を組み合わせて，素数を配列に格納する方法

です。特に，整数が素数かどうかを判定するときは，2からその整数の正の平方根の整数部分までの数で割り切れるかを調べればよいことを理解しておきましょう。

基本情報技術者試験の学習におすすめの参考書

基本情報技術者試験の合格を目指す方におすすめの参考書です。