150709

Ruby


素数の個数(4)

少し改良してみた。

念のため、

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

（実行時間は30分ほどかかる。）

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

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

      # h[n / j]は「i = jのときのh[n]に呼び出されるまでは計算しておく」ことにし、

      # i = jのとき、h[n / (j + 1)]から計算していくことにする

      keys[i..-1].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

def A040014(n)

  (1..n).map{|i| pi(Math.exp(i).to_i)}.unshift(0)

end

ary = A040014(29)

# OEIS A040014のデータ

ary0 =

[0,1,4,8,16,34,79,183,429,1019,2466,6048,14912,

 37128,93117,234855,595341,1516233,3877186,9950346,

 25614562,66124777,171141897,443963543,1154106844,

 3005936865,7842921261,20496470801,53645077679,

 140599114669]

# 一致の確認

p ary == ary0