「AP過去問 令和6年度秋期 午後 問3 プログラミング」の版間の差分
| 52行目: | 52行目: | ||
この関数prime1の時間計算量は、Nを用いて表すと<i>O</i>(<span style="display: inline-block; border: 2px solid; padding-left: 20px; padding-right: 20px;">ア</span>)である。 | この関数prime1の時間計算量は、Nを用いて表すと<i>O</i>( <span style="display: inline-block; border: 2px solid; padding-left: 20px; padding-right: 20px;">ア</span> )である。 | ||
| 87行目: | 87行目: | ||
/* メイン処理開始 */</br> | /* メイン処理開始 */</br> | ||
while (d が N 以下)</br> | while (d が N 以下)</br> | ||
if (<span style="display: inline-block; border: 2px solid; padding-left: 20px; padding-right: 20px;">イ</span>)</br> | if ( <span style="display: inline-block; border: 2px solid; padding-left: 20px; padding-right: 20px;">イ</span> )</br> | ||
primesの末尾にdの値を追加する</br> | primesの末尾にdの値を追加する</br> | ||
t ← d × d</br> | t ← d × d</br> | ||
| 97行目: | 97行目: | ||
d ← d + 1</br> | d ← d + 1</br> | ||
endwhile</br> | endwhile</br> | ||
/* メイン処理終了 */</br> | /* メイン処理終了 */</br> | ||
return primes</br> | return primes</br> | ||
</td> | </td> | ||
2024年11月17日 (日) 00:09時点における版
AP 過去問題 午後に戻る。
AP過去問_令和6年度秋期_午後_問2_経営戦略の同じ回の前の問題へ移動。
AP過去問_令和6年度秋期_午後_問4_システムアーキテクチャの同じ回の次の問題へ移動。
令和6年度秋期 午後 問3 プログラミング(AIプロンプト向け)
■
令和6年度秋期 午後 問3 プログラミング(問題原文)
■素数を列挙するアルゴリズムに関する次の記述を読んで、設問に答えよ。
素数とは、2以上の自然数のうち、正の約数が1と自身だけである数のことである。
2以上の自然数Nに対して、N以下の素数を列挙する関数prime1のプログラムを図1に示す。なお、本問では、配列の要素番号は1から始まり、要素数が0の配列を{}で表す。
|
〇整数型の配列: prime1(整数型: N) |
この関数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) |
回答・解説
AP過去問_令和6年度秋期_午後_問2_経営戦略の同じ回の前の問題へ移動。
AP過去問_令和6年度秋期_午後_問4_システムアーキテクチャの同じ回の次の問題へ移動。
AP 過去問題 午後に戻る。