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

AP 過去問題 午後に戻る。

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

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

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

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

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

　2以上の自然数Nに対して、N以下の素数を列挙する関数prime1のプログラムを図1に示す。なお、本問では、配列の要素番号は1から始まり、要素数が0の配列を{}で表す。ただし、プログラムは変数宣言や配列操作が日本語表現されている部分がある特殊なプログラムです。if構文内の処理条件やwhileのループ継続条件も日本語で表記されています。また← は 一般的なプログラミング言語の=と同じ意味です。

図1　関数prime1のプログラム ここから(表のプログラム中の全角スペースは半角スペースと同じ意味)

〇整数型の配列: 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　/*(L1)*/
　　endwhile
　　if (isPrime が true と等しい)
　　　primes の末尾にdの値を追加する
　　endif
　　d ← d + 1
　endwhile
　/* メイン処理終了 */
　return primes

図1　関数prime1のプログラム ここまで

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

[アルゴリズムの改良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に示す。

図2　関数prime2のプログラム ここから(表のプログラム中の全角スペースは半角スペースと同じ意味)

〇整数型の配列: 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 ← [ウ]　/*(L2)*/
　　　endwhile
　　endif
　　d ← d + 1
　endwhile
　/* メイン処理終了 */
　return primes
図2　関数prime2のプログラム ここまで

　関数prime2は関数prime1と比較してメイン処理部の時間計算量を小さくすることができ、引数Nの値が同一の場合において、関数prime2の(L2)の行の実行回数は関数prime1の(L1)の行の実行回数以下となる。

[アルゴリズムの改良2]

　4以上の偶数は全て2の倍数であるので、素数ではない。したがって2以外の素数を列挙するためには奇数だけを考慮すればよい。この性質を利用して、関数prime2に次の変更を加えた関数prime3を考える。

(1)　関数の戻り値として素数の一覧が格納されるprimesにあらかじめ2を格納しておく。

(2)　いずれのループも奇数についてだけが実行されるようにする。

(3)　3以上の自然数2k+1が素数か否かをisPrime[k]で表すようにする。

　関数prime3のプログラムを図3に示す。

図3　関数prime3のプログラム　ここから(表のプログラム中の全角スペースは半角スペースと同じ意味)

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

図3　関数prime3のプログラム　ここまで

　関数prime3は関数prime2と比較してメイン処理部の二重ループの実行回数を減らすことができる。引数Nの値が同一の場合において、関数prime3の(L3)の行の実行回数は、関数prime2の(L2)の行の実行回数の半分以下となる。加えて、計算に必要な配列isPrimeの要素数も半分以下に減らすことができる。

設問1　本文中の [ア] に入れる適切な字句を答えよ。

設問2　図2中の [イ] 、 [ウ] に入れる適切な字句を答えよ。

設問3　図3中の [エ] ～ [カ] に入れる適切な字句を答えよ。

設問4　prime1(20)、prime2(20)、prime3(20)をそれぞれ実行したとき、図1中の(L1)の行、図2中の(L2)の行、図3中の(L3)の行が実行される回数をそれぞれ答えよ。

　

令和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　　　　　　　　　(L1) 　　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 ← ウ　　　　　　　　　(L2) 　　　endwhile 　　endif 　　d ← d + 1 　endwhile 　/* メイン処理終了 */ 　return primes

図2　関数prime2のプログラム

　関数prime2は関数prime1と比較してメイン処理部の時間計算量を小さくすることができ、引数Nの値が同一の場合において、関数prime2の(L2)の行の実行回数は関数prime1の(L1)の行の実行回数以下となる。

[アルゴリズムの改良2]

　4以上の偶数は全て2の倍数であるので、素数ではない。したがって2以外の素数を列挙するためには奇数だけを考慮すればよい。この性質を利用して、関数prime2に次の変更を加えた関数prime3を考える。

(1)　関数の戻り値として素数の一覧が格納されるprimesにあらかじめ2を格納しておく。

(2)　いずれのループも奇数についてだけが実行されるようにする。

(3)　3以上の自然数2k+1が素数か否かをisPrime[k]で表すようにする。

　関数prime3のプログラムを図3に示す。

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

図3　関数prime3のプログラム

　関数prime3は関数prime2と比較してメイン処理部の二重ループの実行回数を減らすことができる。引数Nの値が同一の場合において、関数prime3の(L3)の行の実行回数は、関数prime2の(L2)の行の実行回数の半分以下となる。加えて、計算に必要な配列isPrimeの要素数も半分以下に減らすことができる。

設問1　本文中の ア に入れる適切な字句を答えよ。

設問2　図2中の イ 、 ウ に入れる適切な字句を答えよ。

設問3　図3中の エ ～ カ に入れる適切な字句を答えよ。

設問4　prime1(20)、prime2(20)、prime3(20)をそれぞれ実行したとき、図1中の(L1)の行、図2中の(L2)の行、図3中の(L3)の行が実行される回数をそれぞれ答えよ。

　

回答・解説

　プログラムが3つに分かれていて、それぞれの動きを理解しなければならないことと、問題文で数学的用語が使われるので、何を言っているか理解する力を試される問題です。素数の性質を明確に理解していない人は素数の仕組みを改めて考えることになる問題でもあったと思います。トレースする時間がかかるので中程度と高難度の間くらいの難易度かなと思います。管理人は、試験の最後に取り組んだのですが、時間がなくて焦って全然だめでした。ふふふ。悔しい。この程度の問題も解けずに撃沈するとはね。最初の一問だけサービス問題かなと思いました。楽に答えられましたが、他は適当に埋めたら、適当に間違ってました。そうそう感覚的に答えれる問題でもないわな。最後の実行回数なんかはトレースする時間がなければ、答えられるわけもなし。この1問に1時間くらいくれればとけてたと思う。

　悔やんでもしょうがないので一問づつ、やっていきましょう。

設問1

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

　の穴埋めなので、prime1関数のNが増えた時にどれくらいの計算量になるかを考える問題です。ループの部分に注目するとwhileが二重になっているということへの気づきが大事になってきます。そしてその繰り返し構造がどうなっているかを見極めるだけです。ループの設定を読み解いてみましょう。

　一つ目のループは(dがN以下)となっています。Nは計算量のNと同じ位置づけなので最初に与えられる関数の引数Nです。後の問題で出てくるprime1(20)を基準に考えると、dは初期値が2なので、2から20までの計算量O(N)が一つ目のループだけの計算量といえます。dはループの終端で毎回1づつ増加するので、ループの回数は2～20までをステップ1づつで処理しています。

　二つ目のループは(tがd未満)です。tは毎回、初期値が2にリセットされる一定の繰り返し開始値で、ステップ値は1です。dは2からはじまってNまでをステップ1づつ増加していく値です。未満なので、最初はt=2、終了条件は2未満なので0回で、1回と繰り返し回数が増えていってNが20の場合は最後の終了条件はd=20のときです20未満となります。

　つまり、prime1(20)のNが20のときの例でみると一つ目のループと二つ目のループは以下のような仕組みで繰り返されます。

ループ1のdの値	ループ2が実行されるときのtの値
2
3	2
4	2, 3
5	2, 3, 4
6	2, 3, 4, 5
7	2, 3, 4, 5, 6
8	2, 3, 4, 5, 6, 7
9	2, 3, 4, 5, 6, 7, 8
10	2, 3, 4, 5, 6, 7, 8, 9
11	2, 3, 4, 5, 6, 7, 8, 9, 10
12	2, 3, 4, 5, 6, 7, 8, 9, 10, 11
13	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
14	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
15	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
16	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
17	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
18	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17
19	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18
20	2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19

　という感じで、2回目の繰り返しの終了値がNではなく1づつ大きくなってNになるまでという仕組みなので、N2とまではいかないですが、計算量はN2に概ね従うことがわかります。具体的な繰り返し回数だけで見ると (N-1)(N-2)/2 で (N2-3N+2)/2という回数です。時間計算量として見る時はN2以外、つまり最も計算量に影響する値以外の具体的な回数は無視することになっています。したがって答えは

ア N2

　です。Order(N2)のような表現方法がわかっていないとつらい問題だったと思いますが、直感的に答えれるのはせいぜいここまででしょう。具体的に繰り返し回数を計算するには、上記に示した表まで思い描く時間が必要です。表のようなものが繰り返し回数だとわかれば最後の問題にも答えられようものです。計算式を導き出せなくても、N=20なら1+2+…+18を1回だけちまちま計算すればよいことです。

設問2

　関数prime2の穴埋めです。プログラムの穴埋めというのは、そこで何をしようとしているかという推測と、具体的なつじつまの合う値を見つけ出すことにあります。まずはその周辺のプログラムがどのようなことをしているのか流れを読む必要があります。読み解いていきましょう。問題文にも何をしようとしているか説明がついている部分もあるので、照らし合わせて理解していきます。

　まず最初の方で各種変数の初期化をしています。何に使おうとしているかをひとつづつ予測しながら確認します。

1行目はprimesに空っぽの配列を格納しています。コメントにも結果となる素数の一覧を格納する配列だと説明があるので、N=20の場合、プログラムの関数がreturn文にまで進んだ時には

• primes={2, 3, 5, 7, 11, 13, 17, 19}

　になるものです。

2行目はisPrimeの最初の要素だけfalseの配列を格納しています。配列の要素番号が1から始まるということなので、isPrime[1]=falseということです。素数の性質として1は素数ではないし、問題文でも素数は2以上の値であると説明がされていますのでfalseで矛盾もありませんので、この値をあとのプログラム内で書き換える必要もない状態で初期化されていると認識できます。

3行目・4行目はcとdを2という値で初期化しています。ここだけでは何故2で初期化する変数が2個準備されるのかわかりませんが、素数の始まりが2からなので、それに関連して2から始まってるのかな程度の予想しかできません。

次に5行目でtが初期化せずに宣言されています。何かに使うらしい。程度でしょうか。

次は短めのwhile文が始まります。c が N 以下であるのがループの条件になっています。N=20 なら c は20を超えたら終了しそうですね。それと3行目で謎に初期化された変数を使っていますね。そしてループの中でcはひとつづつ増やすという c ← c + 1 のような処理がなされています。c は繰り返し処理の制御に使う変数で 2から始まって、N以下の間、N=20 なら c は 2, 3, 4 , ... , 19, 20 と変化して、21になるとループが終わります。その中で isPrime の末尾に true を設定しています。isPrime[k]は素数であるかどうかの結果を格納する変数なのに全部にtrueが設定されています。これは問題文のPrime2関数の(1)の条件2以上N以下の自然数について、全て “素数である” とマークする。とあるところの処理だと認識できます。

　6行目から9行目のwhile文を実行することによって

• isPrime={false, true, true, true, true,

true, true, true, true, true,

true, true, true, true, true,

true, true, true, true, true}

　というように全て “素数である” とマークしたことになります。つまり、初期化の一部ってことになります。c は初期化のために使うループ制御のための変数だったことになります。ということは d はメイン処理で使う。2から始まる変数としておくと便利なモノとして使われるということが予測できます。

　10行目からのwhile文はプログラムの最後まで繰り返しの範囲となっている長いwhile文です。早速、ループ条件としてdが使われていますね。d が N 以下。c と同じようなループ条件です。そして、プログラムの終わりにあるendwhileの手前でd ← d + 1となっていますので、変数 c の使われ方と同じです。どうやら問題文の(2)2以上N以下の自然数dについて、次の(a)、(b)を行う。に相当するループであると解釈できそうです。

　11行目は問題になっているイが使われる条件のif文です。この if が成立したときだけ、この長いwhile文の中での処理をする長い区間を制御する条件であると読み取れます。d が 2, 3, 4 , ... , 19, 20 と変化して、21になるとループが終了する中でのif文なので、変数 d の値を使うとif文の条件が変化するので、d を使いそうな予感はします。t はまだ初期化されてもないし値を保持していないので条件にはなりそうにないですね。問題文の(2)の(a)と(b)の条件を判定してif文の中で①②を処理しているのでは？と考えることができれば答えは見えてきます。

　dが “素数ではない” とマークされている場合、何もしない。 と dが “素数である” とマークされている場合、次の処理を行うとある条件のdとプログラム中のdは役割も同じということにたまたま行きつくとうことですね。すると予め初期化していた。isPrimeの要素d番目がtrue(isPrime[k]が素数であるを意味するtrue)だったら条件が成立するとすれば、うまく行きそうです。そして、プログラム中のwhile文の中でisPrime[k]を先にfalseにしてしまえば、もう素数の候補ではないと処理することもできそうです。

　イには isPrime[d]がtrueと等しい という条件をif文に設定するとよいことになります。

　そして問題文のとおり処理をすすめるなら①の処理dが素数であることを確定させる。を実行することになるのですが、既にtrueに設定されているので、isPrime配列に対しては何もすることはないですね。最初はd=2のときにif文が成立して、2は素数であることを確定して②の処理をして次にすすめば、2の倍数は素数でないとして潰すことができそうです。

　12行目では最初のd=2のときを想定しても素数として確定する意味で primesの末尾にdの値を追加する 処理が実施されています。

• primes={2}

　のように最初の2は確定されそうです。

　13行目では t ← d × d として d=2の場合は t が 4になります。素人目線だと2の倍数を潰していくなら t ← d + dでいいんじゃないのと思ってしまいますが、3の倍数の3*2や5の倍数の5*2、5*3、5*4や7の倍数の7*2、7*3、7*4、7*5、7*6は既に潰されているので、潰していく際の初期値は d × d で問題ない訳です。なるほど！って関心してる場合じゃないで、次いこかって問題文は言ってます。

　14行目から17行目のwhile文では倍数にあたる部分をisPrime[k]をfalseにしていく処理になっています。

　tがN以下の間、falseにしていく処理をするというループ条件になっています。d=2の場合はd × d で 4、そして6、8、10、12、14、16、18、20に対応するisPrime[k]をfalseにして、d=3のときは d × d で 9、そして12、15、18に対応するisPrime[k]をfalseにして、d=5の場合は d × d で 25なのでfalseにしていく処理は無し。d=7の場合も d × d で49でfalseは無し。d=11の場合も d × d で121でfalseは無し。d=13の場合も d × d で169でfalseは無し。d=17の場合も d × d で289でfalseは無し。d=19の場合も d × d で361でfalseは無し。という感じの処理を行います。

　16行目は問題の部分ですが、ここまでくるとtでdの倍数をつぶしていくので、t ← t + d でtにdの倍数をひとつづついれて行く処理をすることになります。

ウ t + d です。

　以上が回答になります。したがって

イ isPrime[d]がtrueと等しい

ウ t + d

　が回答になります。

　追いかける余裕があれば、回答できそうな問題ですね。あーでものちの繰り返し回数問題の回答に影響しそうなひとひねりがあるのがいやらしいですよね。t ← d × dですでに計算した部分を省略しようとするところですね。素数3以降の倍数の潰し方が単純に3, 6, 9, 12 ... や5で10, 15, 20, 25 ... といった潰し方ではないところは大事なポイントにもなりますね。手順の要約が問題文にあるので、それと対応していけば答えられる問題ではありました。このあたりは中程度の難易度ですね。でも、この説明くらい深く理解していれば次の問題も楽に回答できる手筈になっているようです。

設問3

　改良したprime3の穴埋め問題です。prime2を奇数だけを考えるバージョンに変更するだけです。2は素数であらかじめ決定しておいて、2の倍数を消す作業を省略するだけですね。

　2は素数で決まっているので、最初の初期化で

• primes ← {2}
• c ← 3
• d ← 3

　と初期化が変わっています。

　isPrimeの初期化ループでは c = 3 から c = c + 2 のステップで c が N 以下の間繰り返し、isPrimeの末尾にtrueを追加する形式で

• isPrime={　　　true, true, true, true　/* 　　　　　　 k=1 2k+1= 3, k=2 2k+1= 5, k=3 2k+1= 7, k=4 2k+1= 9 */

true, true, true, true, true} /* k=5 2k+1=11, k=6 2k+1=13, k=7 2k+1=15, k=8 2k+1=17, k=9 2k+1=19 */

　という具合に初期化します。

　10行目の長いループでは、dは3から3, 5, 7, ... , 17, 19 と変化して N以下の間、繰り返します。ループの終端でd ← d + 2となっているので、初期値3からステップ値2になることも認識できます。

　11行目のif文の条件となるエについて prime2では isPrime[d]がtrueと等しい でしたが、d=3のときはisPrimeの要素番号1を参照し、d=5のときはisPrimeの要素番号2を参照するように工夫しなければなりません。整数型の演算結果 3 / 2 = 1.5 が 1として扱われますし、5 / 2 = 2.5 が 2 と扱われますが、そのまま計算結果を要素番号にするなら、割り切れる演算できちんと 1 にしなければなりません。(3 - 1) / 2 = 1, (5 - 1) / 2 = 2, (7 - 1) / 2 = 3, ... , (17 - 1) / 2 = 8, (19 - 1) / 2 = 9 となることに気づきが必要となりまして、

エ isPrime[(d - 1) / 2]がtrueと等しい

　というのが回答になります。2分の1の偶数を算出するための「ひらめき」が必要ですね。

　次の2行は prime2 関数とまったく同じで問題ないですね。そして、奇数3, 5, 7, ... , 17, 19のそれぞれの倍数を潰す処理をするためにd = 3のときは t ← 3 * 3 で t = 9を潰して、12, 15, 18, 21と潰しますが、12と18は偶数なので潰す必要がありませんし、潰そうと思ってもisPrimeの要素には偶数の値に対応する要素がないので、12と18のような偶数は処理をとばす必要があります。ちなみに21はN=20のときは、もう範囲外なので潰しませんがNがもう少し大きい指定の場合の動作として、9, 15, 21と潰すように動作するといいことになり、15と9の差分は6で、21と15の差分も6です。したがってt ← t + 2 × dで潰せば奇数だけを潰していけます。5のときも t ← 5 * 5 で t = 25を潰して 30, 35, 40, 45と潰していく必要ありますが、30と40は偶数で潰す必要はありません。そうすると、25, 35, 45と潰すように動作するといいことになり、35と25の差分は10で、45と35の差分も10です。したがって、5以降の奇数の素数もt ← t + 2 × dという増分で潰すことで問題はないことがわかります。したがって

カ　t ← t + 2 × d

　というのが回答になります。先にカを割り出しましたが、オの部分はprime2のプログラムではisPrime[t] ← falseでしたが、isPrimeの要素番号を指すには、エの回答のやり方をマネして、素数 t のisPrimeの要素番号は半分の値の整数だったので、isPrime[(t - 1) / 2] ← false と指定することになります。したがって

オ　(t - 1) / 2

　というのが回答になります。プログラムの問題は考え方があってるのにケアレスミスで一部分を落とすことはあるかもしれませんが、一蓮托生(いちれんたくしょう)ですので、設問2と設問3がすべて答えられないとイ～オの5問は答えられないでしょう。ということで答えは

エ isPrime[(d - 1) / 2]がtrueと等しい

オ　(t - 1) / 2

カ　t ← t + 2 × d

　これが答えです。奇数だけに着目するとたしかにループの回数も相当に減るんですね。素数の算出って、ちょっとした工夫でここまで簡単なループになるんすね。スゴイぜ。問題制作者。やるな！実に面白い。

設問4

　は繰り返し処理の回数を正確に回答する問題ですね。prime1の(L1)はかなりの回数が処理されますので、計算式があったほうが楽ですが、1+2+3+...+17+18でいいことも説明したとおりです。ループの初期値で一回処理して、ループを脱出する値になるまで t が増加して出ていく感じであることを認識できていれば間違えることなく数えれるでしょう。tのループ中の最初の値から最後の値で数えても間違いませんが、厳密なイメージとしては(L1)も(L2)も(L3)も初期値の算出の処理はされませんので、2回目の値算出からループを脱出する値の算出をするまでの回数です。

(L1)

　計算式は2個目のwhileの最後の繰り返し回数の(N-1)と、1個目のwhileが2個目のwhileを呼び出す回数(N-2)の積に対しての半分の回数が計算式ですので、(N-1)(N-2)/2です。

N=20の場合は

(20-1)×(20-2)÷2

=19*18÷2

=19*9

=171

　合計171回

(L2)

　素数2の計算をしているときはtの初期値はt ← d × d の計算で 4 です。そして(L2)部のtの値が以下の値に変化します。

• 6、8、10、12、14、16、18、20、22(9回)

　素数3の計算をしているときはtの初期値はt ← d × d の計算で 9 です。そして(L2)部のtの値が以下の値に変化します。

• 12、15、18、21(4回)

　合計13回

(L3)

　素数3の計算をしているときはtの初期値はt ← d × d の計算で 9 です。そして(L2)部のtの値が以下の値に変化します。

• 15、21(2回)

　合計2回

　したがって、

(L1)　171

(L2)　13

(L3)　2

　L1はプログラムの穴埋めがわからなくても全部のプログラムが掲載されているので追いかけるだけなので答えれた可能性はありますが、L2とL3はプログラムの穴埋めがわからないと算出するのはほぼ不可能でしょう。ヒントとしてはL3の回数はL2の半分以下というヒントしかないのでよっぽどの魔術師でないと無理です。

　この問題は時間さえあれば解けるレベルの中級の難度と思います。素数の求める処理の流れの日本語が理解できないとか、意味を汲み取るのに時間がかかると解けなかったかもしれません。設問1だけはプログラムの雰囲気とOrderが理解できれば答えれたかもしれません。まぁ設問1だけしか解けないとか管理人と同じレベルだった人は不合格まっしぐらだったでしょう。時間をかけなくても、とけるようになるまで頑張りましょう！ちなみにAIは即答できない問題もありました。配列番号が1から始まるのが苦手なようです。それと処理回数の計算も苦手っぽいです。この日本語プログラムが苦手なのだと思います。IPAの日本語プログラムを理解できるわれわれ人間はAIをまだ上回れる！

　

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

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

AP 過去問題 午後に戻る。