応用情報技術者 2013年 春期 午前2 問07

エラトステネスの篩のループ設定【午前2解説】

正解の理由

解法ステップ

1. 目的を確認：配列 A に対して合成数（素数でない数）を 0 にして、最終的に A[k] ≠ 0 の k を素数として出力する。
2. 内側ループの増分 c は「m の倍数だけを消す」ので c = m が必須。
3. 内側ループの終値 b は全体の上限 100 を超えないように b = 100 が自然（b が小さいと高い k を除去できない）。
4. 内側ループの始点 a は「素数 m 自身を消さない」かつ「m の倍数を全てカバーする」位置であること。
   • a = m は最初の反復で k = m となり、素数 m を消してしまうため不可。
   • a = 2m は k = 2m, 3m, ... と進み、m 自身は含まれないので正しい（ただし効率面で m^2 の方が望ましい）。
5. 上の条件から a＝2m、b＝100、c＝m（選択肢 イ）が妥当と判断。

選択肢別の誤答解説

• ア（a＝2、b＝m²、c＝1）
  内側ループが step 1 で 2 から $m^2$ まで順に消すため、例えば m=2 のとき k=2 が消されて素数 2 を消してしまいます。また step 1 は m の倍数のみを消す意図に反し、非該当の数（素数含む）まで消去してしまいます。よって不適。
• イ（a＝2m、b＝100、c＝m）
  各 m について 2m, 3m, ... を 100 まで消去し、m 自身は消さない。外側を $2\le m\le 10$ としてあるので 100 以下の合成数は必ずどれかの m によって消去され、正しく動作します。したがって正解。
• ウ（a＝m、b＝m²、c＝m）
  内側ループの初期値が a＝m のため、k の最初の値が m になり A[m]=0 として素数 m 自体を消してしまいます（例えば m=3 のとき k=3 が最初に来る）。これが決定的な誤りです。なお b＝m² を終値にする設計は効率化の観点では有益ですが、a が m だと致命的に不適です。
• エ（a＝m²、b＝100、c＝1）
  c＝1 によって m² から 100 までの全ての数を順に消去してしまい、m² 以上の多くの素数まで消されます。特に m=2 の初回で 4 から 100 をすべて消すため大半の数が消えてしまい目的を満たさない設計です。

よくある誤解

• 「始点は必ず 2m」：動作としては 2m でも正しいが、効率的実装では $m^2$ を始点にするのが一般的。$m^2$ より小さい m の倍数は既に小さい素因数で消去済みだからです。
• 「a = m にしても大丈夫」：a = m にすると最初の k が m になり素数 m 自体を消してしまう点を見落としやすい。
• 「終値は m² で十分」：終値を m² にすると高い k（例：m が小さいときの大きな合成数）を消し残す可能性があるため、上限（ここでは 100）を終値にするか、内側ループの回数設定を工夫する必要がある。

補足コラム

def sieve(n):
    A = [True] * (n+1)
    A[0] = A[1] = False
    m = 2
    while m*m <= n:
        if A[m]:
            for k in range(m*m, n+1, m):  # a = m*m が効率的
                A[k] = False
        m += 1
    return [i for i, isprime in enumerate(A) if isprime]
print(sieve(100))

FAQ