【Ruby】エラトステネスさんの篩にかければ素数が振ってくる

エラトステネスの篩

素数を求めるためのアルゴリズムです．
以下のステップ（wiki参照）を踏むことで簡単に素数を求めることができます．

1. 探索リストに2から*x*までの整数を昇順で格納

2. 探索リストの先頭の数を素数リストに移動し，その倍数を探索リストから篩い落とす

3. 上記の篩い落とし操作を探索リストの先頭値が*x*の平方根に達するまで行う

4. 探索リストに残った数を素数リストに移動して処理終了

実際のコード

def sieve_of_eratosthenes(until_number)
  prime_num_list = (2..until_number).to_a
  0.upto(prime_num_list.size - 1) do |i| 
    break if prime_num_list[i] >= Math.sqrt(until_number)    
    prime_num_list = prime_num_list.reject{ |num| num % prime_num_list[i] == 0 && num != prime_num_list[i] }
  end
  prime_num_list
end

おわりに

プロコンって，アルゴリズムを知っているか知らないかで本当に差が出ますよね