平成25年度 春期 応用情報技術者試験 午前 問7
テクノロジ／アルゴリズム配列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; （注：本サイトでは原問題の表を文字表記に変換しています）
出典：平成25年度 春期 応用情報技術者試験 午前 問7
- アa：2，b：m²，c：1
- イa：2m，b：100，c：m
- ウa：m，b：m²，c：m
- エa：m²，b：100，c：1
正解：イ
解説
内側のforループでは，mの倍数（2m，3m，…）に対応する配列要素を0にすることで合成数を除外するエラトステネスのふるいを実装しています。倍数は2m以上100以下をm刻みで進む必要があるため，a＝2m，b＝100，c＝mが正解です。
選択肢ごとの解説
- ア誤り。a＝2，c＝1では，mに関わらず2から100までの全要素を0にしてしまい，素数まで消してしまいます。
- イ正しい。mの倍数である2m，3m，…，100をm刻みで0にすることで合成数だけを除外できます。
- ウ誤り。a＝m，b＝m²ではmの倍数を正しく網羅できず，除外すべき合成数を取りこぼします。
- エ誤り。a＝m²，c＝1では，m²から100までの連続した整数をすべて0にしてしまい，mの倍数以外も消してしまいます。