素数を列挙するアルゴリズム

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

2以上の自然数Nに対して，N以下の素数を列挙する関数prime1のプログラムを図1に示す。なお，本問では，配列の要素番号は1から始まり，要素数が0の配列を{}で表す。

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

〔アルゴリズムの改良1〕

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

関数prime2のプログラムを図2に示す。

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

〔アルゴリズムの改良2〕

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

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

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