応用情報技術者午前過去問演習【サクトレWeb】
平成25年度春期　問7 / 80

平成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 b c
ア 2 m² 1
イ 2m 100 m
ウ m m² m
エ m² 100 1

キーボード：1〜4 で解答　→ 次の問題　← 前の問題

正解と解説を見る

正解：イ

この手続はエラトステネスのふるいです。まず A[2]～A[100] をすべて 1（素数候補）にし，m ＝ 2～10 について m の倍数のうち m 自身を除くもの を 0（合成数）にします。

100 以下の合成数は必ず √100 ＝ 10 以下の素因数をもつので，m を 10 まで調べれば十分です。m の倍数を消すには，初期値 2m，終値 100，増分 m とします。

  • ア: a ＝ 2，b ＝ m²，c ＝ 1
    誤り。2 から m² までのすべての k を 0 にするので，素数も消されてしまいます（m ＝ 10 なら 2～100 がすべて 0 になります）。

  • イ: a ＝ 2m，b ＝ 100，c ＝ m
    正しい。m の倍数のうち m 自身を除く 2m，3m，… を 100 まで 0 にします。m ＝ 2～10 で繰り返すと，100 以下の合成数はすべて 10 以下の素因数をもつので消され，素数だけが残ります（エラトステネスのふるい）。

  • ウ: a ＝ m，b ＝ m²，c ＝ m
    誤り。初期値が m なので，m ＝ 2，3，5，7 のときに素数である m 自身まで 0 にしてしまいます。また m² までしか消さないので 100 以下の倍数を消し切れません。

  • エ: a ＝ m²，b ＝ 100，c ＝ 1
    誤り。m² 以上のすべての k を 0 にするので，例えば m ＝ 2 のとき 4 以上の素数 5，7，… も消えてしまいます。

答え

イ: a ＝ 2m，b ＝ 100，c ＝ m

出典：平成25年度 春期 応用情報技術者試験 午前 問7

平成25年度春期の他の問題