トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

数論

[アルゴリズム,数論]

練習のための問題は 競技プログラミングの履歴

数論

整数の性質とか、素数とか、そのへんはここにまとめる

  エラトステネスの篩

100万以下のすべての素数を列挙してみる

def erastosthenes(n)
  array = (2..n).to_a
  threshold = Math.sqrt(n)
  count = 2
  while threshold > count
    array.reject!{|n| n != count and n % count == 0}
    count += 1
  end
  array
end

PN = erastosthenes(1000000)

puts PN.length
puts PN[10000]
お名前: コメント: