« Project Euler - Problem 46 | トップページ | Project Euler - Problem 48 »

2009年8月 3日 (月)

Project Euler - Problem 47 : 3.5s (Ruby 1.9)

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


詳しい証明は省略しますが、連続する数について次のことが言えます。

  • 連続する 2 つの自然数は共通因数を持たない。(互いに素である)
  • 連続する 2 つの正の奇数は共通因数を持たない。(互いに素である)
  • 連続する 2 つの正の偶数は共通因数として 2 のみを持つが、ひとつは 21 * a の形をとり、もうひとつは 2n * b (ただし n ≧ 2) の形をとる。

以上のことから、連続する 4 つの数はすべて異なる素因数を持つことになります。

ですから、この問題では素因数分解したときの因数の数だけを調べればいいことになります。

require 'math_tool' n = 2 * 3 * 5 * 7 factors = [n.factorize.size, (n + 1).factorize.size, (n + 2).factorize.size, (n + 3).factorize.size] while true if factors.all?{|i| i == 4} puts n exit end n = n + 1 factors.shift factors.push((n + 3).factorize.size) end

« Project Euler - Problem 46 | トップページ | Project Euler - Problem 48 »

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

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

« Project Euler - Problem 46 | トップページ | Project Euler - Problem 48 »

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            
フォト

最近のトラックバック

無料ブログはココログ