150707

Ruby


素数の和(1)

10＾n 未満の素数の和を求めてみた。
オンライン整数列大辞典の
A046731（http://oeis.org/A046731/list）
と比較し、答え合わせしてみる。

（実行時間の関係で、n = 10＾11, … , 10^15 のときの比較は行なっていません。）

def sum_of_primes(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 * (i + 1) / 2 - 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] -= i * (h[j / i] - hp)

        }

    end

  }

  h[n]

end

def A046731(n)

  (1..n).map{|i| sum_of_primes(10 ** i - 1)}.unshift(0)

end

ary = A046731(10)

# OEIS A046731のデータの一部

ary0 =

[0,17,1060,76127,5736396,454396537,37550402023,

 3203324994356,279209790387276,24739512092254535,

 2220822432581729238]

# 一致の確認

p ary == ary0