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

2009年8月 5日 (水)

Project Euler - Problem 49 : 0.1s (Ruby 1.9)

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


以下の説明の中で「数を構成する数字を小さい順に並べたもの」を「数の組成」という言葉で表現していますが、これは説明を簡単にするために私が勝手に使っている言葉で、きちんとした定義があるわけではありません。(ちなみに 4512 の組成は 1245 となります)


初めに、素数と素数の組成をペアにして配列に入れます。このペアを組成を使ってソートすると、同じ組成を持つ素数のグループが塊になって並びます。

そうしておいて、同じ組成のグループだけを取り出して等差数列ができるかどうかを調べていきました。

既に同じ組成の数が集まっている分、探す手間が省けるので結構速く答えが出ます。

(自作の "math_tool.rb" に関してはこちらをご覧ください)

require 'math_tool' p_lst = prime_list(9999).drop_while{|i| i < 1000} p_lst = p_lst.map{|i| [i, i.to_a.sort.to_i]}.sort_by{|x| x[1]} ans = Array.new until ans.size == 2 arr = p_lst.take_while{|a| p_lst[0][1] == a[1]}.map{|a| a[0]} len = arr.size p_lst = p_lst.drop(len) next if len < 3 arr = arr.sort while arr.size >= 3 a = arr.shift arr.each do |b| c = b + (b - a) ans.push([a, b, c]) if arr.include?(c) end end end p ans

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

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

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

« Project Euler - Problem 48 | トップページ | Project Euler - Problem 50 : 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            
フォト

最近のトラックバック

無料ブログはココログ