sieve

sieve.rb

def sieve( n )
  s = (2..n).to_a
  s.each { |p| next unless p; break if p**2 > n; (p**2).step(n, p) { |m| s[m-2] = nil } }
  s.compact
end

def time
  start = Time.now
  yield
  Time.now - start
end

primes = [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, 101, 103, 107, 109, 113]

puts "sieve ran in #{time { sieve 2**10 }} seconds and is #{sieve(120) == primes}"