エラトステネスの篩

sieve.rb

def sieve(num)
  ary = Array.new(num, true)
  ret = []
  ary.each_with_index do |b, i0|
    next if i0 == 0 || !b
    p = i0+1
    ret.push p
    i0.step(num, p) do |mark|
      ary[mark] = false
    end
  end
  ret
end

p sieve 100
# [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]

require 'prime'

p Prime.each(100).map {|p| p}
# [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]