Tbpgr Blog

Employee Experience Engineer tbpgr(てぃーびー) のブログ

Ruby | Rubyでエラトステネスの篩(ふるい)を実装してみる

概要

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