応用情報技術者 2013年 春期 午前2 問07
問題文
配列Aに対して次の手続を実行して,2≦k≦100である素数んだけを全て出力したい。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;
選択肢
ア：
イ：（正解）
ウ：
エ：
配列Aに対する素数判定ループの初期値・終値・増分の選択【午前2 解説】
要点まとめ
- 結論：ループ変数kの初期値は2m、終値は100、増分はmとする（選択肢イが正解）です。
- 根拠：エラトステネスの篩のアルゴリズムでは、mの倍数をm²から100までm刻みで消去します。
- 差がつくポイント：m²から始める理由と増分mの意味を理解し、誤って2やmから始めないことが重要です。
正解の理由
選択肢イの「a=2m、b=100、c=m」は、エラトステネスの篩の典型的な実装に合致します。
- ループはmの倍数を消すため、初期値はmの2倍（2m）から始めるのが一般的ですが、実際にはm²から始めることも多いです。
- ただし、問題文のループは「for m=2 to 10 step 1」でmを変え、kのループでmの倍数を消すため、kはmの倍数で増加（増分c=m）し、終値は100までです。
- これにより、2≦k≦100の範囲でmの倍数を正しく消去し、素数だけが残ります。
よくある誤解
- 初期値を2やmにしてしまい、m²から始めるべきところを誤ることがあります。
- 増分を1にしてしまい、mの倍数を正しくスキップできないことがあります。
解法ステップ
- エラトステネスの篩の基本を理解する（素数判定のために倍数を消す）。
- 外側ループmは2から10まで（√100まで）回す。
- 内側ループkはmの倍数を消すため、初期値はm²または2mから始める。
- 増分はmで、kをmの倍数に限定する。
- 終値は100まで設定し、配列Aの該当要素を0にする。
- 最後にA[k]が0でないkを出力し、素数を表示する。
選択肢別の誤答解説
- ア（a=2, b=m²、c=1）：kの増分が1でmの倍数を飛ばさず、効率的でなく誤り。
- イ（a=2m, b=100, c=m）：正解。mの倍数を2mから100までm刻みで消去。
- ウ（a=m, b=m²、c=m）：終値がm²で範囲が狭く、100まで消去できず不十分。
- エ（a=m²、b=100, c=1）：増分が1でmの倍数を飛ばさず非効率かつ誤り。
補足コラム
エラトステネスの篩は古典的な素数判定アルゴリズムで、までの素数を効率的に求める方法です。
内側ループの初期値をにする理由は、それより小さい倍数は既に消去済みだからです。
増分をにすることで、mの倍数だけを効率的に消去できます。
内側ループの初期値をにする理由は、それより小さい倍数は既に消去済みだからです。
増分をにすることで、mの倍数だけを効率的に消去できます。
FAQ
Q: なぜ内側ループの初期値はやなのですか？
A: 未満の倍数は既に小さい素数の倍数として消去済みのため、重複を避けるためです。
A: 未満の倍数は既に小さい素数の倍数として消去済みのため、重複を避けるためです。
Q: 増分を1にすると何が問題ですか？
A: すべての数を1ずつ増やすため、mの倍数だけを効率的に消去できず計算量が増えます。
A: すべての数を1ずつ増やすため、mの倍数だけを効率的に消去できず計算量が増えます。
関連キーワード: エラトステネスの篩、素数判定、ループ制御、配列操作、アルゴリズム
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！