150708

Ruby


素数の個数(3)

（確認する順序が逆になってしまったが、）

オンライン整数列大辞典の
A000720（http://oeis.org/A000720/list）
と比較し、答え合わせしてみる。

def pi(n)

  m = Math.sqrt(n).to_i

  keys = (1..m).map{|i| n / i}

  keys += (1..keys[-1] - 1).to_a.reverse

  h = {}

  keys.each{|i| h[i] = i - 1}

  (2..m).each{|i|

    if h[i] > h[i - 1] # このときiは素数

      hp = h[i - 1]

      i2 = i * i

      keys.each{|j|

        break if j < i2

        h[j] -= h[j / i] - hp

      }

    end

  }

  h[n]

end

def A000720(n)

  (1..n).map{|i| pi(i)}

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