160220

Ruby


素数の個数(6)

http://ijmcs.future-in-tech.net/9.2/R-RuizSondow.pdf
に載っていた等式を用いて素数の個数を求めてみた。
（注意：この方法は以前の方法に比べて大変遅い。）

オンライン整数列大辞典の

A000720（http://oeis.org/A000720/list）
と比較し、答え合わせしてみる。

def A000720(n)
  ary = [0]
  s = 0
  (2..n).each{|j|
    t = 2
    (1..j).each{|i|
      t -= j / i - (j - 1) / i
    }
    s += t / j + 1
    ary << s
  }
  ary
end
ary = A000720(78)

# OEIS A000720のデータ
ary0 =
[0,1,2,2,3,3,4,4,4,4,5,5,6,6,6,6,7,7,8,8,8,8,9,9,
 9,9,9,9,10,10,11,11,11,11,11,11,12,12,12,12,13,13,
 14,14,14,14,15,15,15,15,15,15,16,16,16,16,16,16,
 17,17,18,18,18,18,18,18,19,19,19,19,20,20,21,21,
 21,21,21,21]
# 一致の確認
p ary == ary0