150707(2)

Ruby


素数の個数(1)

e＾n 未満の素数の個数を求めてみた。
オンライン整数列大辞典の
A040014（http://oeis.org/A040014/list）
と比較し、答え合わせしてみる。
（実行時間は35分ほどかかる。）

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 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

p ary0

# 大雑把に求めた近似値

p (1..29).map{|i| (Math.exp(i) / i).to_i}.unshift('?')

出力結果

true

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

, 595341, 1516233, 3877186, 9950346, 25614562, 66124777, 171141897, 443963543, 1

154106844, 3005936865, 7842921261, 20496470801, 53645077679, 140599114669]

["?", 2, 3, 6, 13, 29, 67, 156, 372, 900, 2202, 5443, 13562, 34031, 85900, 21793

4, 555381, 1420879, 3647776, 9393805, 24258259, 62800749, 162950583, 423687106,

1103713422, 2880195973, 7528061901, 19705490392, 51652038010, 135563251625]