sieve_of_eratosthenes.rb

def sieve(limit)
  return [] if limit < 2

  is_prime = Array.new(limit + 1) do |i|
    i == 2 || i.odd?  # mark 2 and all odd numbers true, everything else false
  end

  max = Math.sqrt(limit).floor
  (3..max).step(2) do |p|
    next unless is_prime[p]

    (p * p).step(limit, 2 * p) do |multiple|
      is_prime[multiple] = false
    end
  end

  [2] + (3..limit).step(2).select { |n| is_prime[n] }
end

puts sieve(30).inspect
# => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]