Ruby x 以下の素数をすべて求める

メリークリスマスイブ

# エラトステネスのふるい
# 求めたい数の平方根以下の素数の倍数を取り除いた数が素数
# 素数の倍数を取り除く
# 2 ならば 4, 6, 8, 10 ... を取り除く
# 3 ならば 6, 9, 12, 15 ... を取り除く
target = 10000000
a = Array.new(target + 1, 1)

k = 2
while (k * k) <= target
  i = k
  while i <= (target / k)
    a[k*i] = 0
    i += 1
  end
  begin
    k += 1
  end while a[k] == 0
end

i = 2
while i <= target
  if a[i] == 1
    print "#{i} "
  end
  i += 1
end