odiak's blog

AOJ 0056: Goldbach's Conjecture

AOJ(Aizu Online Judge)の0056をRubyで解いてみました。

入力nが与えられ、足してnになる素数の組が何通りあるかを出力する問題です。

ついでにゴルフもしてみました。

require"prime";h={};(q=Prime.take 5133).map{|x|h[x]=!!1};while 0<n=gets.to_i;p q.count{|x|x<=n/2&&h[n-x]}end

整理すると

require "prime"
h = {}
q = Prime.take 5133
q.each do |x|
  h[x] = true
end
while (n = gets.to_i) > 0
  p q.count{|x| x <= n / 2 && h[n - x]}
end

nが5000以下であることを利用して、最初に素数を確保しておきます。最初はこの素数の配列に.include?を使って素数かどうかの判定をしていましたが、TLEになってしまった。include?は要素を一つずつ調べていくので遅いのは当然ですね。

そこで、それぞれの素数をHashのキーにしてtrueを入れておけば、一瞬で検索できることに気付き、やってみると見事Acceptしました。

RubyでCodeGolfするの楽しいですね!