« Project Euler - Problem 11 | トップページ | Project Euler - Problem 13 »

2009年6月17日 (水)

Project Euler - Problem 12

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


ここにも書いてあるように、素因数分解の結果がわかれば、約数の個数が出せます。

例えば、素因数分解の結果が [[2, 2], [3, 1]] だった場合、

[[2, 2], [3, 1]].inject(1){|pr, n| pr * (n[1] + 1)}

とすることで個数が出ます。


ということで、何のひねりもなく素直にコーディングすると次のようになりました。

"math_tool.rb" に関してはここを見てください。

require 'math_tool' tri = 0 1.upto(1.0/0) do |i| tri = tri + i # 三角数を加算で表現。 if tri.factorize.inject(1){|pr, n| pr * (n[1] + 1)} > 500 then puts(tri) break end end

私のパソコン上で Ruby 1.9 を使って実行すると、約 1.6 秒で答が出ます。


ところで、この問題にはもっと高速に答えを出す方法があります。

ヒントは……

  • 三角数の一般式は T(n) = n * (n + 1) / 2
    • 当然、T(n+1) = (n + 1) * (n + 2) / 2
  • n と n + 1 は「互いに素」になる。
    • n が偶数の場合、n / 2 と n + 1 は「互いに素」になる。
    • n が奇数の場合、n と (n + 1) / 2 は「互いに素」になる。
  • 整数 a と整数 b が「互いに素」となる場合、(a の約数の数) * (b の約数の数) = (a * b) の約数の数

これらの考えを基にコーディングした結果、約 0.3 秒で答が出ました。


このアルゴリズムは、他のブログに付いていたコメントがヒントになって生まれました。

自分だけでこんなアルゴリズムを考えつけるくらいの数学的知識が欲しいなぁ……。

« Project Euler - Problem 11 | トップページ | Project Euler - Problem 13 »

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: Project Euler - Problem 12:

« Project Euler - Problem 11 | トップページ | Project Euler - Problem 13 »

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

最近のトラックバック

無料ブログはココログ