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

2009年8月12日 (水)

Project Euler - Problem 51 : 1.1s (Ruby 1.9)

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


8 つの素数を見つけるということは、置き換えられる数字が 8 種類あるということです。

一の位に偶数や 5 があるとその数は偶数または 5 の倍数となってしまいます。したがって一の位は 1, 3, 7 ,9 のいずれかになるので、一の位が置換されることはありません。

また、0 から 9 までの数字のうち 8 個の数字が出現するのですから、その中の一番小さい数は 0, 1, 2 のいずれかになります。

そこで、0, 1, 2 のいずれかを 2 個以上含む素数を見つけたら、実際に他の数で置換して素数になるかどうかを調べてみます。

require 'prime' require 'math_tool' Prime.each do |n| arr = n.to_a # 0, 1, 2 の位置を探す ( 一の位は調べない ) pos_arr = [[], [], []] arr[0 .. -2].each_with_index do |v, i| pos_arr[v].push(i) if v < 3 end # 同じ数字を置換して、素数を探す。 pos_arr.select{|a| a.size > 1}.each do |pos| 2.upto(pos.size) do |r| # 同じ数字が 2 個以上あった場合、2 個変えた場合、3 個変えた # 場合……と、全ての組み合わせを考える。 pos.combination(r).each do |a| nums = Array.new (0 .. 9).each do |n| a.each{|i| arr[i] = n} nums.push(arr.to_i) unless arr[0] == 0 end select_nums = nums.select{|n| n.prime?} if select_nums.size == 8 # p select_nums puts select_nums[0] exit end end end end end

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

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

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

« Project Euler - Problem 50 : 0.1s (Ruby 1.9) | トップページ | Project Euler - Problem 52 : 0.4s (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            
フォト

最近のトラックバック

無料ブログはココログ