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

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

　素数とは，2以上の自然数のうち，正の約数が1と自身だけである数のことである。
　2以上の自然数Nに対して，N以下の素数を列挙する関数 prime1 のプログラムを図1に示す。なお，本問では，配列の要素番号は1から始まり，要素数が0の配列を{}で表す。　この関数 prime1 の時間計算量は，Nを用いて表すとO(ア)である。

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

• 2以上N以下の自然数について，全て"素数である"とマークする。
• 2以上N以下の自然数dについて，次の(a)，(b)を行う。
  
  1. dが"素数ではない"とマークされている場合，何もしない。
  2. dが"素数である"とマークされている場合，次の処理を行う。
     1. dが素数であることを確定させる。
     2. d以上の自然数xについて，dをx倍した数を"素数ではない"とマークする。

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

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

• 関数の戻り値として素数の一覧が格納される primes にあらかじめ2を格納しておく。
• いずれのループも奇数についてだけ実行されるようにする。
• 3以上の自然数2k＋1が素数か否かを isPrime[k] で表すようにする。

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

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

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

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

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