« Project Euler - Problem 36 : 0.1s (Ruby 1.9) | トップページ | Project Euler - Problem 38 : 0.1s (Ruby 1.9) »

2009年7月22日 (水)

Project Euler - Problem 37 : 0.09s (Ruby 1.9)

問題はこちらをご覧ください。


この問題は以前 Scheme で Project Euler を解いていた時にも記事にしましたが、改めて Ruby ならこうなるということで……。

とりあえず、問題文を素直に解釈したコードは次のようになりました。

require 'prime' require 'math_tool' class Integer def check? d = 1 while true d = d * 10 q, r = self.divmod(d) return true if q == 0 return false unless (q.prime? and r.prime?) end end end ans = Array.new Prime.each do |n| next if n < 10 unless n.to_a.any?{|i| i > 2 and i.even?} ans.push(n) if (n.prime? and n.check?) end break if ans.size == 11 end puts ans.inject(:+)

このコードで工夫したのは以下の二点です。

  • "Integer#check?" で右から切り詰める場合と左から切り詰める場合を一度に調べる。
  • 調べる数に 2 以外の偶数が含まれている場合は切り詰める過程で必ず素数でなくなるので、予め調べる対象から除外する。

このコードでも Ruby 1.9 なら約 2.4 秒で答えが出ますが、もう少し考える余地があります。


詳しい考察はここを読んでいただきたいのですが、以下のコードのように条件に合う素数を作っていく方法でかなりの高速化が可能です。

# -*- coding: utf-8 -*- require 'math_tool' class Integer # * 左から切り詰める場合の逆の動作でチェックする。 def check? d = 1 begin d = d * 10 m = self % d return false unless m.prime? end until m == self return true end end # * 整数 n の右に数字を付けて素数を作る。 # * 右から切り詰める場合の逆の動作。 def make_new_prime(p) arr = [1, 3, 7, 9].map{|x| p * 10 + x} return arr.select{|i| i.prime?} end lst = [2, 3, 5, 7] # 一桁の素数 arr = Array.new until lst.empty? lst = lst.map{|i| make_new_prime(i)}.inject(:+) arr = arr + lst end ans = arr.select{|i| i.check?} puts ans.inject(:+)

このコードでは Ruby 1.9 で約 0.08 秒で答えが出ます。

数学だけではないのでしょうが、答えを出す方法は一つではないんですよね。

« Project Euler - Problem 36 : 0.1s (Ruby 1.9) | トップページ | Project Euler - Problem 38 : 0.1s (Ruby 1.9) »

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/45708249

この記事へのトラックバック一覧です: Project Euler - Problem 37 : 0.09s (Ruby 1.9):

« Project Euler - Problem 36 : 0.1s (Ruby 1.9) | トップページ | Project Euler - Problem 38 : 0.1s (Ruby 1.9) »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ