令和6年度 秋期 応用情報技術者試験 午後問題 問3 エラトステネスの篩と計算量の改善

エラトステネスの篩などの素数判定アルゴリズムを評価する際、処理の効率（計算量）を考えることが重要です。

• 素朴な判定アルゴリズム（prime1など）では、ある数 $N$ に対して $2$ から $N-1$ まで試し割りを行うため、処理全体の手間は $N$ の2乗、すなわち $N^2$ に比例して増加します。
• この計算量 $N^2$ を削減し、効率的に素数を求める手法としてエラトステネスの篩などが活用されます。

高得点のポイント

• アルゴリズムの実行回数や計算量が $N$ に対してどのように増加するかを理解していること
• 適切な数式表現（$N^2$）で簡潔に記述できていること

エラトステネスの篩（prime2）において、素数を見つけた際にその倍数をふるい落とす処理を行います。

• 配列 isPrime は、各インデックスの値が素数であるかどうかを true または false の論理値で保持しています。
• 対象となる数 d が素数であるかを判定するためには、配列の要素 isPrime[d] が true であるかを確認する必要があります。

高得点のポイント

• 判定対象となる配列 isPrime とインデックス d を正しく指定できていること
• 条件式として「trueと等しい」ことを論理的に記述できていること

素数 d の倍数をふるい落とすためのループ更新処理です。

• 変数 t は d の倍数を表すインデックスとして用いられます。
• 現在の倍数 t に対して、次の倍数を求めるためには d を加算する必要があるため、更新式は t+d となります。

高得点のポイント

• エラトステネスの篩における倍数の走査方法を理解していること
• ループ内で次の倍数を求める加算処理（t+d）を正しく記述できていること

奇数のみを対象とした効率化アルゴリズム（prime3）における素数判定処理です。

• 偶数（$2$ 以外）は素数ではないため、奇数のみを配列に保持することでメモリと処理時間を節約できます。
• 奇数 $k$ は、インデックス $i = (k-1) \div 2$ に対応づけられます。
• したがって、奇数 d が素数であるかを判定するには、isPrime[(d-1)÷2] が true であるかを確認します。

高得点のポイント

• 奇数のみを保持する配列のインデックス変換規則を正しく理解していること
• プログラムの条件式として正確に記述できていること

見つかった素数 d の倍数 t をふるい落とす際に、対象となる配列のインデックスを計算する処理です。

• t は d の奇数倍であり、これもまた奇数です。
• 奇数のみを管理する配列 isPrime において、奇数 t が格納されているインデックスは、変換規則に基づき (t-1)÷2 となります。

高得点のポイント

• ふるい落とす対象の値 t を、対応する配列のインデックスへ変換する数式を理解していること
• 括弧を用いた正しい演算順序で式を記述できていること

奇数のみを扱う効率化アルゴリズムにおいて、次のふるい落とし対象となる倍数を計算する処理です。

• 素数 d （奇数）の倍数のうち、偶数倍はすでに除外されているため、奇数倍のみをたどる必要があります。
• 現在の奇数倍 t に d を足すと偶数倍になってしまうため、2×d を足して次の奇数倍へと進めます。
• したがって、更新式は t+2×d となります。

高得点のポイント

• 奇数の奇数倍のみを走査するためには、2×d ずつ加算する必要があるという数学的性質を理解していること
• それをプログラムの更新式として正しく記述できていること

関数 prime1(20) における素朴な素数判定処理のループ実行回数を求める問題です。

• prime1 では、各整数 $n$ について、$2$ から $n-1$ までの数で割り切れるかを判定します。
• $n = 2, 3, 4, \dots, 20$ について、内側のループ（行 L1）の実行回数はそれぞれ $0, 1, 2, \dots, 18$ 回となります。
• これらの合計を求めると、$0 + 1 + 2 + \dots + 18 = \frac{18 \times 19}{2} = 171$ となり、実行回数は 171 回です。

各選択肢の解説

本問は数値による記述式解答であるため、固定の選択肢はありませんが、以下のような誤答が想定されます。

• 境界値の誤り: ループの終了条件を $n$ までの包含として計算してしまった場合など、等差数列の項数を見誤る計算ミスに注意が必要です。

関数 prime2(20) （エラトステネスの篩）における倍数のふるい落とし処理（行 L2）の実行回数を求める問題です。

• 素数 $d$ の倍数を $t = d^2$ から走査する最適化が適用されているものとします。（$d=2$ の場合は $t=4$）
• $d = 2$ の場合：$t = 4, 6, 8, 10, 12, 14, 16, 18, 20$ の 9回 実行されます。
• $d = 3$ の場合：$t = 3^2 = 9$ から始まり、$t = 9, 12, 15, 18$ の 4回 実行されます。
• $d = 4$ は素数でないためスキップされます。
• $d = 5$ の場合：$t = 5^2 = 25$ となり、上限の $20$ を超えるため実行されません。
• 合計すると、$9 + 4 = 13$ となり、実行回数は 13 回です。

各選択肢の解説

本問は数値による記述式解答であるため、固定の選択肢はありませんが、以下のような誤答が想定されます。

• 開始位置の誤り: 最適化を考慮せず、すべての素数で $t=2d$ から数えてしまうと、重複して実行回数を多く見積もる誤答につながります。

関数 prime3(20) における、奇数のみを対象としたふるい落とし処理（行 L3）の実行回数を求める問題です。

• このアルゴリズムでは、$2$ を除く奇数（$3, 5, \dots, 19$）のみを配列で管理します。
• $d = 3$ の場合：最適化により $t = d^2 = 9$ から始まり、$2d = 6$ ずつ加算されます。対象となる $t$ は $9, 15$ の 2回 のみです。（次は $21$ となり範囲外）
• $d = 5$ の場合：$t = 5^2 = 25$ となり、開始時点で上限 $20$ を超えるため実行されません。
• 以降の奇数についても同様に実行されないため、全体の実行回数は 2 回となります。

各選択肢の解説

本問は数値による記述式解答であるため、固定の選択肢はありませんが、以下のような誤答が想定されます。

• ステップ幅の誤り: 奇数倍のみをたどるための $+2d$ のステップ幅を見落とし、$t$ の増加を小さく見積もってしまう計算ミスに注意が必要です。