問題プレビューID: 735d7148応用情報技術者試験 2013年(平成25年度)春期 午前

問 7
応用情報技術者試験 2013年(平成25年度)春期 午前

配列 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;
解説

正解は「イ」です。

これはエラトステネスの篩(ふるい)のアルゴリズムです。まず全ての k を素数候補として A[k] = 1 にし,m を 2 から 10 まで動かしながら,m の倍数を合成数として A[k] = 0 にしていきます。

各 m について,m 自身は素数なので消してはいけません。消すのは m×2,m×3,… という m の倍数です。したがって,初期値は 2m,終値は 100,増分は m となり,a = 2m,b = 100,c = m の「イ」が正解です。

  • ア・ウ: 増分が 1 や m で初期値・終値が合わず,倍数を正しく消せません。
  • エ: 増分が 1 なので m の倍数以外も消してしまい,素数だけを残せません。

関連問題

本文が同じ・似ている問題を表示しています