省メモリで「エラトステネスの篩」同等の結果を得るコード

prime_table.rb

def prime_table(n)
  return []  if n < 2
  return [2] if n == 2
  table = [2, 3]
  i, step = 5, 2
  while i <= n
    guard = Math.sqrt(i).to_i
    table.each do |prime|
      break if (i % prime).zero?
      if prime > guard
        table << i
        break
      end
    end
    i += step
    step = 6 - step
  end
  table
end

prime_table(1000_0000)