演習(エラトステネスの篩)のヒント

出典: CourseWiki

sieveは以下の処理を行います.(細部は少しあいまいに書いてあります)

  • まず,大きさnのboolean型の配列 sieve を確保.
    • これが篩のための配列になります
    • i (0 <= i < n) が素数なら sieve[i] == true に,そうでなければ false になるようにするのがこのメソッドの仕事
  • 一旦,sieve の全ての要素を true にしておく
  • 0と1は素数ではないので,sieve[0]とsieve[1]はfalseにしておく.
  • 以下を繰り返す(for文).
    • 最小の素数2からはじめる(p=2).
    • sieve[p] == true ならば,pは素数である.sieve上でpの倍数(2*p, 3*p ...)は素数ではないのでfalseにする.(最初はp=2なので,sieve[4] = false, sieve[6] = false, ...)
    • pに1を加えながら,上の処理を繰り返す.
  • 最後に sieve を return して終了.

倍数をfalseにする処理も繰り返し処理なので,2重ループになります. 2重ループがややこしければ,倍数をfalseにする処理を別のメソッドにしても構いません.

ナビゲーション