CodeIQやってみた

「コード・トライアスロン」数学の問題

　CodeIQで面白そうな問題があったのでチャレンジ。素数列に関連した関数の定義を与えられてそれを実装する問題。実行時間制限のある問題だったがメモ化再帰したら通った。実行時間4.66秒と何とか及第点の結果だがもう少し高速化できそう。以下は提出コード。

my_code.rb

require 'prime'


@cache_f = { 0 => 3, 1 => 0, 2 => 2 }
def f(n)
  @cache_f[n] ||= f(n - 2) + f(n - 3)
end


@cache_p = []
def get_p(n)
  raise unless n > 0
  until @cache_p[n - 1]
    i = @cache_p.last || (2 - 1)
    begin
      i += 1
    end until f(i) % i == 0
    @cache_p << i
  end
  f(@cache_p[n - 1])
end


def g(n)
  Prime.prime_division(n).map{|a| a[0] }.max
end


def h(n)
  raise unless n > 0
  prime_cache = []
  prime_prime = []
  Prime.each.with_index do |p, i|
    break if p > n
    prime_cache << p
    prime_prime << p if prime_cache.include?(i + 1)
  end
  prime_prime.inject(0){|s,i| s + i }
end




P = get_p(30)
Q = g(P)
R = h(Q)

puts "P: #{P}, Q: #{Q}, R: #{R}"