2024年 秋期 応用情報技術者試験 問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
この関数prime1の時間計算量は、Nを用いて表すとO(ア)である。
[アルゴリズムの改良1]
素数の定義によって、2以上の自然数sについて、s自身を除くsの正の倍数は、1とs以外にsも約数を含むので素数ではない。この性質を利用して関数prime1を改良し、次の手順で素数を列挙する関数prime2を考える。
-
2以上N以下の自然数について、全て"素数である"とマークする。
-
2以上N以下の自然数dについて、次の(a)、(b)を行う。
- (a) dが"素数ではない"とマークされている場合、何もしない。
- (b) dが"素数である"とマークされている場合、次の処理を行う。
- ① dが素数であることを確定させる。
- ② d以上の自然数xについて、dをx倍した数を"素数ではない"とマーク する。
○整数型の配列: 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
関数prime2は関数prime1と比較してメイン処理部の時間計算量を小さくすることができ、自然数Nの値が同一の場合において、関数prime2の(L2)の行の実行回数は、関数prime1の(L1)の行の実行回数以下となる。
[アルゴリズムの改良2]
4以上の偶数は全て2の倍数であるので素数ではない。したがって、2以外の素数を列挙するためには奇数だけを考慮すればよい。この性質を利用して、関数prime2に次の変更を加えた関数prime3を考える。
-
関数の戻り値として素数の一覧が格納されるprimesにあらかじめ2を格納しておく。
-
いずれのループも奇数についてだけ実行されるようにする。
-
3以上の自然数2k+1が素数か否かをisPrime[k]で表すようにする。
○整数型の配列: 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
関数prime3は関数prime2と比較してメイン処理部の二重ループの実行回数を減らすことができる。自然数Nの値が同一の場合において、関数prime3の(L3)の行の実行回数は、関数prime2の(L2)の行の実行回数の半分以下となる。加えて、計算に必要な配列isPrimeの要素数も半分以下に減らすことができる。