問題プレビューID: ae4f55d3応用情報技術者試験 2024年(令和6年度)秋期 午後

問 3
応用情報技術者試験 2024年(令和6年度)秋期 午後

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

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

図 1 関数 prime1 のプログラム

○整数型の配列: 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(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(整数型: 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 を考える。

(1) 関数の戻り値として素数の一覧が格納される primes にあらかじめ 2 を格納しておく。

(2) いずれのループも奇数についてだけ実行されるようにする。

(3) 3 以上の自然数 2k+1 が素数か否かを isPrime[k]で表すようにする。

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

図 3 関数 prime3 のプログラム

○整数型の配列: 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 の要素数も半分以下に減らすことができる。

設問1

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

設問2

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

設問3

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

設問4

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

模範解答

設問1 ア N2N^2

設問2 イ isPrime[d]が true と等しい,ウ t+d

設問3 エ isPrime[(d-1)÷2]が true と等しい,オ (t-1)÷2,カ t+2×d

設問4 (L1) 171,(L2) 13,(L3) 2

解説

素数を列挙するアルゴリズムであるエラトステネスの篩(ふるい)を題材に,素数の性質を利用した効率化の手法についての理解を問う。

設問1では,関数 prime1 は d ごとに 2 以上 d 未満の t で割り切れるかを試す二重ループであり,時間計算量は O(N2)O(N^2) である。

設問2の[イ]は,d が“素数である”とマークされているかの判定であり,isPrime[d]が true と等しいことである。[ウ]は,d の倍数を順にマークするための更新であり,t+d である。

設問3では,奇数のみを扱い,3 以上の自然数 2k+1 が素数か否かを isPrime[k] で表す。[エ]は d に対応するマークの判定であり,isPrime[(d-1)÷2]が true と等しいことである。[オ]は t に対応する添字であり,(t-1)÷2 である。[カ]は,偶数を飛ばして奇数の倍数のみをマークするための更新であり,t+2×d である。

設問4では,N=20 のときの (L1),(L2),(L3) の各行の実行回数は,それぞれ 171 回,13 回,2 回である。

関連問題

本文が同じ・似ている問題を表示しています