素数を列挙するアルゴリズムに関する次の記述を読んで，設問に答えよ。
素数とは，2以上の自然数のうち，正の約数が1と自身だけである数のことである。
2以上の自然数Nに対して，N以下の素数を列挙する関数prime1のプログラムを図1に示す。なお，本問では，配列の要素番号は1から始まり，要素数が0の配列を{}で表す。
図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に示す。
図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は関数prime2と比較してメイン処理部の二重ループの実行回数を減らすことができる。引数Nの値が同一の場合において，関数prime3の（L3）の行の実行回数は，関数prime2の（L2）の行の実行回数の半分以下となる。加えて，計算に必要な配列isPrimeの要素数も半分以下に減らすことができる。
設問1 本文中の ア に入れる適切な字句を答えよ。
解答・解説
解答例
N²
解説
ー
設問2 図2中の イ ， ウ に入れる適切な字句を答えよ。
解答・解説
解答例
イ：isprime[d]がtrueと等しい
ウ：t+d
解説
ー
設問3 図3中の エ 〜 カ に入れる適切な字句を答えよ。
解答・解説
解答例
エ：isprime[(d-1)÷2]がtrueと等しい
オ：(t-1)÷2
カ：t+2×d
解説
ー
設問4 prime1(20)，prime2(20)，prime3(20)をそれぞれ実行したとき，図1中の（L1）の行，図2中の（L2）の行，図3中の（L3）の行が実行される回数をそれぞれ答えよ。
解答・解説
解答例
L1：171 L2：13 L3：2
解説
ー
IPA公開情報
出題趣旨
素数は，数学における学問的な用途のほか，暗号処理の分野などで活用されている。
本問では，素数を列挙するアルゴリズムの一つであるエラトステネスの篩を題材として，素数の性質を利用した効率化の手法についての理解を問う。
採点講評
未公開
