好きなことをして生きる。 - Tech Blog

技術メモと技術ログと趣味ブログ

Algorithm Ruby

[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
LINEで送る
Pocket

-Algorithm, Ruby