エラトステネスの篩

am

Rubyで「エラトステネスの篩」を実装しました。単純な版♪

def sieve(m)
  prime = (0..m).to_a
  (2..m).each do |p|
    next if not prime[p]
    yield(p) if block_given?
    (p+p..m).step(p) do |k|
      prime[k] = false
    end
  end
  prime[2..m].find_all {|p| p}
end

sieve(50) { |p| print "#{p}, " }; puts
#=> 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,

p sieve(50)
#=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]