AP過去問 令和6年度秋期 午後 問3 プログラミング

AP 過去問題 午後に戻る。

AP過去問_令和6年度秋期_午後_問2_経営戦略の同じ回の前の問題へ移動。

AP過去問_令和6年度秋期_午後_問4_システムアーキテクチャの同じ回の次の問題へ移動。

令和6年度秋期 午後 問3 プログラミング(AIプロンプト向け)

■

　

令和6年度秋期 午後 問3 プログラミング(問題原文)

■素数を列挙するアルゴリズムに関する次の記述を読んで、設問に答えよ。

　素数とは、2以上の自然数のうち、正の約数が1と自身だけである数のことである。

　2以上の自然数Nに対して、N以下の素数を列挙する関数prime1のプログラムを図1に示す。なお、本問では、配列の要素番号は1から始まり、要素数が0の配列を{}で表す。

〇整数型の配列: prime1(整数型: N) 　整数型の配列: primes ← {}　　　 /*結果となる素数の一覧を格納する一次元配列 */ 　論理型: isPrime　　　　　　　　 /*ループ内で着目している数が素数か否かを表す変数。 　　　　　　　　　　　　　　　　　　trueであれば、素数であることを表し、falseであれば 　　　　　　　　　　　　　　　　　　素数ではないことを表す*/ 　整数型: d ← 2 　整数型: t 　/* メイン処理開始 */ 　while (d が N 以下) 　　isPrime ← true　　　　　　　　/*仮で素数として扱う */ 　　t ← 2 　　while (t が d 未満) 　　　if (d mod t が 0 と等しい) 　　　　isPrime ← false 　　　endif 　　　t ← t + 1 　　endwhile 　　if (isPrime が true と等しい) 　　　primes の末尾にdの値を追加する 　　endif 　　d ← d + 1 　endwhile 　/* メイン処理終了 */ 　return primes

図1　関数prime1のプログラム

　この関数prime1の時間計算量は、Nを用いて表すとO( ア )である。

[アルゴリズムの改良1] 　素数の定義によって、2以上の自然数sについて、s自身を除くsの正の倍数uは、1とu以外にsも約数に含むので素数ではない。この性質を利用して関数prime1を改良し、次の手順で素数を列挙する関数prime2を考える。

(1) 2以上N以下の自然数について、全て “素数である” とマークする。 (2) 2以上N以下の自然数dについて、次の(a)、(b)を行う。

(a) dが “素数ではない” とマークされている場合、何もしない。

(b) dが “素数である” とマークされている場合、次の処理を行う

① dが素数であることを確定させる。

② d以上の自然数xについて、dをx倍した数を“素数ではない” とマークする。

　関数prime2のプログラムを図2に示す。

〇整数型の配列: prime2(整数型: N) 　整数型の配列: primes ← {}　　　 /*結果となる素数の一覧を格納する一次元配列 */ 　論理型の配列: isPrime ← {false} /*isPrime[k]がtrueであればkが素数であることを 　　　　　　　　　　　　　　　　　　表し、falseであればkが素数ではないことを表す 　　　　　　　　　　　　　　　　　　一次元配列 */ 　整数型: c ← 2 　整数型: d ← 2 　整数型: t 　while (c が N 以下) 　　isPrimeの末尾にtrueを追加する 　　c ← c + 1 　endwhile 　/* メイン処理開始 */ 　while (d が N 以下) 　　if ( イ ) 　　　primesの末尾にdの値を追加する 　　　t ← d × d 　　　while (t が N 以下) 　　　　isPrime[t] ← false 　　　　t ← ウ 　　　endwhile 　　endif 　　d ← d + 1 　endwhile 　/* メイン処理終了 */ 　return primes

図2　関数prime2のプログラム

　

回答・解説

　

AP過去問_令和6年度秋期_午後_問2_経営戦略の同じ回の前の問題へ移動。

AP過去問_令和6年度秋期_午後_問4_システムアーキテクチャの同じ回の次の問題へ移動。

AP 過去問題 午後に戻る。