200209

Crystal


素数の和(2)

以前のRuby のコードをCrystal のコードにかえて出力してみた。

require "big"

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 = Hash(Int32, BigInt).new
  keys.each{|i|
    j = i.to_big_i
    h[i] = j * (j + 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

time = Time.local
p (0..9).map{|i| sum_of_primes(10 ** i)}
puts Time.local - time

出力結果
[0, 17, 1060, 76127, 5736396, 454396537, 37550402023, 3203324994356, 279209790387276, 24739512092254535]
00:00:02.812922000