応用情報技術者 2024年 秋期 午後 問03

解答の論理構成

1. 問題文には
   「この関数prime1の時間計算量は、Nを用いて表すとO(ア)である。」
   とあり、ア を求める設問です。
2. 関数prime1の主要部は
   ① 変数dを2からNまで1ずつ増やす外側ループ
   ② 変数tを2からd-1まで1ずつ増やす内側ループ
   の二重構造になっています。
3. 外側ループが1回回るたびに、内側ループは最大でd-2回実行されます。
   したがって総実行回数は
   $\sum _{d=2}^N(d-2)=\frac{(N-1)(N-2)}{2}$
   となります。
4. 上式の最高次数項は $\frac{1}{2}{N}^2$ であり、定数倍と低次数項を無視すると
   O($N^2$) に漸近します。
5. よって ア には $N^2$ が入ります。

誤りやすいポイント

• 内側ループの上限を常にNと誤解しO($N^3$) としてしまう。実際には上限がdに比例するため二乗オーダーにとどまります。
• 内側ループがd未満で止まることから、$1+2+\cdots +(N-1)$ の等差数列和になる点を見落とし、O($N\log N$) などと早合点する。
• 定数項や1/2の係数をそのままビッグオー表記に持ち込む（例：O($\frac{1}{2}{N}^2$) と書く）ミス。ビッグオーでは定数倍を省略します。

FAQ

解答の論理構成

• 【問題文】では関数prime2の手順を
  「② d以上の自然数xについて、dをx倍した数を“素数ではない”とマークする。」
  と述べています。
  つまり、既に合成数と分かった数はisPrimeがfalseになっており、まだtrueのまま残っているものだけが候補です。
• したがって (L2) より前に置かれる条件 イ では
  「dが “素数である”とマークされている場合」を判定しなければなりません。
  配列isPrimeの仕様は【問題文】にある
  「isPrime[k]がtrueであればkが素数である」
  なので、判定式は
  isPrime[d]がtrueと等しい
• 内側のwhileループは
  t ← d × d からスタートし、d の倍数を順に潰していく典型的な「エラトステネスのふるい」です。
  1回のループでtを次の倍数に進めるにはdを足せばよいので
  t ← t + d
  が ウ に入る語句となります。
• 以上より
  イ：isPrime[d]がtrueと等しい
  ウ：t+d

誤りやすいポイント

• isPrime[d] を参照せず、誤ってprimesの末尾要素との比較を書いてしまう。
• 内側ループを t ← t * d としてしまい、倍数ではなく指数列を生成して無限ループに陥る。
• t ← d + d と書いて初回だけ正しくても 2 回目以降に t を保持し損ねる実装ミス。

FAQ

解答の論理構成

1. 素数表現のルール確認
   • 問題文には「3以上の自然数2k+1が素数か否かをisPrime[k]で表すようにする」とあります。
   • したがって「奇数2k+1 ⇔ 配列添字k」の対応が決定します。
2. エ の導出
   • ループ変数 d は「3から2ずつ増える奇数」です。
   • 配列添字への変換は $k=\frac{d-1}{2}$。
   • 「isPrime[k] がtrueなら素数と確定」という仕様より
     エ は isPrime[(d-1)÷2] がtrueと等しい になります。
3. オ の導出
   • 内側ループでは t ← d × d からスタートし、以降は奇数の倍数だけを調べます。
   • 配列添字は同じ変換規則で $k=\frac{t-1}{2}$。
   • よって代入対象は isPrime[(t-1)÷2]、中の添字部のみを書くので オ は (t-1)÷2 です。
4. カ の導出
   • 従来のふるいでは $t\leftarrow t+d$ としていましたが、偶数を無視するため倍数の刻み幅は $2d$。
   • したがって カ は t + 2 × d になります。

誤りやすいポイント

• 添字変換を $k=d÷2$ としてしまい偶数混入でバグになる。
• カ を t + d としてしまい、偶数倍を繰り返しマークして性能劣化。
• エ をisPrime[d] と書いてしまい、配列の範囲外アクセスまたは正否逆転を招く。

FAQ

解答の論理構成

1. ループ構造の整理
   • 図1・図2・図3はすべて「素数列挙」のために二重ループを用いる。
   • 計数対象はそれぞれ
     • 図1中の「(L1)」
     • 図2中の「(L2)」
     • 図3中の「(L3)」
       の3行である。
   • いずれも 引数Nに “20” を与えたとき の実行回数を求める。
2. prime1(20) の場合
   • 外側ループは “dが2以上20以下” を順に取る。
   • 内側ループは “t が d 未満” の間だけ回り、「(L1)」＝t ← t + 1 が1回実行されるたびに1カウント。
   • 自然数 $d$ に対し、$t$ は $2,3,\dots ,d-1$ と動くので回数は $(d-2)$。
   • 総回数は = 0+1+2+\dots +18 = \frac{18 \times 19}{2} = 171$$
   • よって (L1) は 171回。
3. prime2(20) の場合
   • 改良で “素数である $d$ を見つけたときだけ” 内側ループをまわし、開始値は “t ← d × d”。
   • さらに「(L2)」の実行は $t$ を $d$ ずつ増やしながら $N$ 以下の倍数を消す” ときだけ。
   • $N=20$ では $\sqrt{20}\simeq 4.47$ であり、$d\times d$ が $20$ 以下になる素数 $d$ は “2” と “3” だけ。
     1. $d=2$ のとき： $t$ は “4,6,8,10,12,14,16,18,20” → 9回
     2. $d=3$ のとき： $t$ は “9,12,15,18” → 4回
     3. $d\ge 5$ は $d\times d>20$ なので０回
   • 合計 9+4 = 13回。
4. prime3(20) の場合
   • さらに “偶数を完全に除外” し、
     • $d$ は “3,5,7,… ” と2ずつ増加
     • 内側ループは “t ← d × d” から 2 × d ずつ増やして奇数倍のみを処理する。
   • $N=20$ では $d\times d\le 20$ を満たす奇素数 $d$ は “3” だけ。
     • $d=3$ のとき： $t$ は “9,15” → 2回
     • $d\ge 5$ は $25>20$ のため０回
   • 合計 2回。
5. 結果のまとめ
   • (L1)：171
   • (L2)：13
   • (L3)：2

誤りやすいポイント

• d × dから始める条件を見落とし、$2d,3d$ など低い倍数も数えてしまう。
• $\sqrt{N}$ まで調べればよい事実を使わず、すべての $d$ で内側ループを考えてしまう。
• prime3の増分が “2 × d” であることに気付かず、“d” で加算したまま計算する。

FAQ