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

2009年8月11日 (火)

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

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


2 から順に素数を足していった時、547 個目の素数を足した時点で和が 100 万を越えてしまいます。

したがって、求める答えは 546 個以下の素数の和になるはずです。

では、どのくらいの素数を用意しておけば良いのでしょうか?

問題文の中では、「連続する素数の和で 1000 未満の素数を表したときに最長になるのは 953 で 21 項を持つ」という表記があります。

話を単純化するために、「連続する 21 個の奇数の和が 100 万未満で一番大きくなる場合」を考えてみます。和が最大になる時、その中に含まれる奇数の最大値を計算すると 47579 になります。

このことから、かなり大雑把に考えても 5 万以下の素数があれば計算には足りそうです。

そこで、5 万以下の素数列を準備し、その中から連続する素数を取り出して実際にその和が素数になるかどうかを調べてみます。

調べる長さは 546 から始めてだんだん減らしていきます。

require 'math_tool' Limit = 100_0000 Max = 5_0000 p_lst = prime_list(Max) p_len = p_lst.size sum = 0 len = p_lst.take_while{|a| sum = sum + a; sum <= Limit}.size len.downto(21) do |i| 0.upto(p_len - i) do |j| sum = p_lst.drop(j).take(i).inject(:+) break if sum > Limit if sum.prime? puts sum exit end end end

実際に答えを計算させると、最初に求めた 546 番目の素数 (3931) より大きな素数は必要ないことが分かるのですが、あえて最初に考えたとおり 50000 までの素数を準備してから答えを計算させました。

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

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

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

« Project Euler - Problem 49 : 0.1s (Ruby 1.9) | トップページ | Project Euler - Problem 51 : 1.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            
フォト

最近のトラックバック

無料ブログはココログ