応用情報技術者 試験情報＆徹底解説

令和６年秋 午後問３の設問３について質問です。
[primesの末尾にdを追加する]より、
素数３はd=3の時にif(エ)をTRUEとなり追加されていると思います。
エ=isPrime[(d-1)/2]=TRUEが答えですが、
なぜisPrime[(3-1)/2]=isPrime[1]=TRUEであるかが分かりません。
while(cがN以下){
isPrimeの末尾にTRUEを追加する。
c=c+2
}
の処理にてisPrime[3]=TRUE,isPrime[5]=TRUE,...となっていると思いますが、
この場合isPrime[1]=FALSEでは無いのですか？
ご教授いただけますと幸いです。

応用情報 令和6年 秋期 午後 問3
https://www.ap-siken.com/kakomon/06_aki/pm03.html

> while(cがN以下){
>   isPrimeの末尾にTRUEを追加する。
>   c=c+2
> }
> の処理にてisPrime[3]=TRUE,isPrime[5]=TRUE,...となっていると思いますが、

いいえ、違います。
そうであるなら isPrime[1], isPrime[2], isPrime[4] が存在しないことになります。

図3 には次の注釈が登場します。
このkに1,2,3,4を代入すると、この日本語は次の意味であることが分かります。

isPrime[1]がtrueであれば3が素数であることを表し、
isPrime[2]がtrueであれば5が素数であることを表し、
isPrime[3]がtrueであれば7が素数であることを表し、
isPrime[4]がtrueであれば9が素数であることを表し、

----
質問者にとって、
初期化時に配列長をあらかじめ決めておく静的な配列は馴染みがあるけれど、

> isPrime ← {}
のように初期化時の配列長は0で、
> isPrime の末尾に true を追加する
のように要素の追加で配列長が伸びていく動的な配列（リスト）は馴染みがないのかな、と思いました。

今回質問があった箇所を、静的な配列としてコーディングするなら次のようになります。

整数型: idx ← 0
while (c が N 以下)
  idx ← idx + 1
  isPrime[idx] ← true
  c ← c + 2
endwhile

補足です。
登場する配列の要素を書いてみます。
N=20として
まず、isPrime[]の初期化処理として

while(cがN以下){
isPrimeの末尾にTRUEを追加する。
c=c+2
}
を行い
isPrime[]={true,true,true,true,true,true,true,true,true}
を作ります。この後、プログラムを実行すると
d=3のとき
isPrime[4]とisPrime[7]が、falseに変わります。
dが5以上の時は,isPrimeに変更はありません。
プログラム実行後は、
isPrime[]={true,true,true,false,true,true,false,true,true}
になります。
primesは、{2,3,5,7,   11,13,   17,19} です。

No.3 の例示が分かりやすいので、設問3の解説を書いてみます。

> isPrime[]={true,true,true,true,true,true,true,true,true}
は、とりあえず初期状態を次のように設定することを表しており、

isPrime[]={
true,  /*  3が素数である */
true,  /*  5が素数である */
true,  /*  7が素数である */
true,  /*  9が素数である */
true,  /* 11が素数である */
true,  /* 13が素数である */
true,  /* 15が素数である */
true,  /* 17が素数である */
true   /* 19が素数である */
}

> d=3のとき
> isPrime[4]とisPrime[7]が、falseに変わります。
は、3が素数だと決まったなら、その後、次のようになることを表している。

isPrime[]={
true,  /*  3が素数である */
true,  /*  5が素数である */
true,  /*  7が素数である */
false, /* isPrime[4]＝ 9は3の倍数なので素数ではない */
true,  /* 11が素数である */
true,  /* 13が素数である */
false, /* isPrime[7]＝15は3の倍数なので素数ではない */
true,  /* 17が素数である */
true   /* 19が素数である */
}

設問3の空欄エ・オ・カは図3の次の箇所に登場している。

【エ】
d＝3 のとき isPrime[1] を指し、
d＝5 のとき isPrime[2] を指し、
d＝7 のとき isPrime[3] を指すような計算式で、isPrime[]の真偽を判定すればよい。
それは【エ isPrime[(d－1)÷2] が true と等しい】

【オ】
d＝3 のとき「t ← d×d」の実行で t＝3×3＝9 になる。
t＝9 のときそれは素数ではない、つまり、isPrime[4]←false を指すような計算式で 配列isPrime[]の指標を求めればよい。
その計算式は エ と同様で【オ (t－1)÷2】

【カ】
配列 isPrime[] の初期状態の意味は、
とりあえず最初は 3,5,7,9,11,13,15,17,19 を素数とみなす(true)というものだった。
3が素数だと決まったなら、その後は、3の倍数である
3×3、3×5、3×7、3×9、3×11 ……は素数でない(false) と【オ】で代入すればよい。
t＝3×3＝9 から始まり 3×5、3×7、3×9、3×11 と変化する計算式は【カ t＋2×d】
（ちなみに No.3 で例示された N＝20 であるなら 3×7＝21 ですでにNを越えているので、
3×3、3×5 で倍数の検証を終了し、3×7、3×9、3×11 までループする必要はない。
これが while (t が N 以下) ）