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

問題文

配列Aに対して次の手続を実行して、2≦k≦100である素数kだけを全て出力したい。a, b, cに入るループの初期値、終値、増分として、適切な組合せはどれか。　 for k = 2 to 100 step 1: 　　　A[k] = 1; for m = 2 to 10 step 1: 　　　for k = [　a　] to [　b　] step [　c　]: 　　　　　　A[k] = 0; for k = 2 to 100 step 1: 　　　if A[k] ≠ 0: 　　　　　　print k;

🖊️ 解答を隠して解いてみる

選択肢

ア：

イ：（正解）

ウ：

エ：

🔒 解説は解答すると表示されます

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

正解の理由

選択肢イ（a＝2m、b＝100、c＝m）は、各mに対してmの倍数だけを2mから100まで隔たりmごとに正しく消去します。外側ループはmを2から10（

100 = 10

）まで回しているため、100以下の合成数は少なくとも一つの小さい素因数mによって消去されます。したがって、最終的にA[k] が0でないkは素数のみ残り、目的どおり2≦k≦100の素数を出力できます。

（補足）内側ループの初期値を

m^{2}

にするのが効率的な実装として一般的ですが、初期値を

2 m

にしても動作的には正しく、ただし小さい倍数に対する重複除去が多くなり非効率になります。ここでは与えられた選択肢の中で「正しく動作する組合せ」を選ぶとイが適合します。

解法ステップ

目的を確認：配列Aに対して合成数（素数でない数）を0にして、最終的にA[k] ≠ 0のkを素数として出力する。
内側ループの増分cは「mの倍数だけを消す」のでc = mが必須。
内側ループの終値bは全体の上限100を超えないようにb = 100が自然（bが小さいと高いkを除去できない）。
内側ループの始点aは「素数m自身を消さない」かつ「mの倍数を全てカバーする」位置であること。
- a = mは最初の反復でk = mとなり、素数mを消してしまうため不可。
- a = 2mはk = 2m, 3m, ... と進み、m自身は含まれないので正しい（ただし効率面でm^2の方が望ましい）。
上の条件から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 \leq m \leq 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）を終値にするか、内側ループの回数設定を工夫する必要がある。

補足コラム

効率的なエラトステネスの篩の実装では、内側ループをa = m*m、c = m、b = N（配列上限）とすることが多いです。理由は、ある合成数xが最小の素因数pを持つとき、x = p * qでありq ≥ pなのでx ≥ p^2です。したがってpより小さい素数での処理によってp*qのうちp*q < p^2のものは既に消されているため、p自身からp^2未満の倍数を再度走査する必要はありません。これにより実行回数が大幅に削減され、全体の計算量は実用的には

O (N lo g lo g N)

程度になります。

参考実装（Python）：

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

Q1: なぜ外側ループは2から10（

100

）まででよいのですか？
A1: 任意の合成数 ≤100は少なくとも一つの素因数 ≤√100を持つため、√Nまでの素因数で十分に消去できます。

Q2: 実装上は2mとm^2のどちらを選べばよいですか？
A2: 両方とも正しくは動きますが、効率を考えるとa =

m^{2}

が推奨されます。教育的には2mと書くことも多いので、選択肢の中身と目的（正しさか効率か）を確認してください。

Q3: c（増分）がmである必然性は？
A3: 目的は「mの倍数だけを消す」ことなので、増分はm（m, 2m, 3m, ...）でなければなりません。増分が1だと倍数以外も消してしまいます。

関連キーワード: エラトステネスの篩、素数探索、ループ設計、アルゴリズム最適化、計算量分析

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

応用情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！