平成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;
- ア a：2，b：m²，c：1
- イ a：2m，b：100，c：m
- ウ a：m，b：m²，c：m
- エ a：m²，b：100，c：1
解答・解説を見る
正解：イ
AI解説
この手続はエラトステネスのふるいである。全要素を1（素数候補）にした後、m＝2〜10について「mの倍数のうちm自身を除く 2m，3m，…，100」を0にして消せば、最後に残った添字が素数になる。したがって初期値a＝2m、終値b＝100、増分c＝m のイが正しい。m自身を消してはいけない点と、100まで全ての倍数を消す点がポイントである。 ア: 終値m²・増分1では、2からm²までを全て消してしまい、素数（2，3，5，7など）まで消してしまう。 イ: 正しい。mの2倍から100まで、mおきに消すことで「m自身を除くmの倍数」だけを消せる。 ウ: 初期値mから消すと、素数であるm自身（m＝2，3，5，7のとき）まで消してしまう。 エ: 初期値m²は篩の高速化で使われる値だが、増分1では倍数以外も全て消してしまうため誤りである。 💡 エラトステネスのふるいは「素数候補の表→各mについてm自身を除く倍数を消す」という流れ。増分がm（倍数だけを飛び飛びに消す）になっているかを最初に確認すると速い。
出典：平成25年度 春期 応用情報技術者試験 午前 問7 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。