エラトステネスの篩をRubyで実装する

エラトステネスの篩(エラトステネスのふるい)は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がある。
エラトステネスの篩 - Wikipedia

アルゴリズム

  1. 探索リストに2からxまでの整数を昇順で入れる
  2. 探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから篩い落とす
  3. 上記の篩い落とし操作を探索リストの先頭値がxの平方根に達するまで行う
  4. 探索リストに残った数を素数リストに移動して処理終了

ソースコード

MAX = 30
target = Array(2..MAX)
prime_numbers = []

LIMIT = Math.sqrt(MAX)
until target.first > LIMIT
  sieve = target.shift
  prime_numbers << sieve
  target.delete_if {|n| (n % sieve).zero? }
end

prime_numbers + target #=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー)

C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー)