概要
Rubyでエラトステネスの篩(ふるい)を実装してみる
内容
エラトステネスの篩(ふるい)は下記の手順で素数を導く
・2から任意の数値Xまでの数列を探索リストに格納する
・探索リストの先頭の要素を素数リストに移動。その倍数を探索リストから篩い落とす
・上記の操作を先頭から取得した要素が、数値Xの平方根になるまで繰り返す
・探索リストに残った数値を素数リストに追加する
コード
# encoding: utf-8 require 'prime' class EratosthenesSieve def self.sieve(max) get_prime([*2..max], []) end def self.get_prime(searches, primes) return primes + searches if searches.first**2 > searches.last primes << searches.shift searches.delete_if {|v|v % primes.last == 0} get_prime(searches, primes) end end primes1 = EratosthenesSieve.sieve(100) print primes1 puts primes2 = *Prime.each(100) # Rubyの標準ライブラリPrimeで生成した素数と比較し、結果を検証 print (primes1 == primes2.to_a) puts
出力
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] true