Project Euler 72, オイラー関数

http://projecteuler.net/index.php?section=problems&id=72

この問題は明示的に書かれてはいないですが、オイラー関数を利用して解く問題のようです。
2〜1000000の各数に互いに素な数の個数を足していくのかぁ、、と思ったときにオイラー関数を思い出しました。

以前、「高速な素数判定」について調べたときに、

というものがあるということを見ていたのでなんとか思い出せました。

ただ、オイラー関数の意味は分かっていても数式化できることを知らなかったので、最初は愚直に

  def phi(n)
    (1..n-1).select do |t|
      gcd(n,t) == 1
    end.size
  end

なんてコードを書きましたが、当然のようにプログラムは終わりませんでした。(O(n^2)かかることになります。ここでは n = 10^6)

そこで調べたところ、オイラー関数の値を数式化したものがちゃんとありました。

http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Euler.html

それにしても、「nと互いに素なn未満の自然数の個数」というのがきちんと数式化できるとか、「aをnと互いに素な整数としたとき、a^φ(n) ≡ 1 mod n が成り立つ」とか、整数論って面白いですね。学生の頃は不勉強だったので何も知らなかったのですが、今更ながらに面白さがわかってきました。

ちなみに、オイラー関数を上記サイトを参考に実装してPE72を解きましたが、私のコードでは Ruby1.9 で 53s かかりました。まあそんなものなのかなぁ、なんて思ってフォーラムを見ていたところ、Cのコードですがすごく短いコードがあったのでRubyに軽く実装して動かしてみたところ 3s で終わりました。。
使っている数学は全く同じでオイラー関数の数式をプログラムに実装しているだけなのに、、これがアルゴリズムというやつか。。と驚愕しました。
ちなみに、私のコードでは素因数分解とオイラー関数と全体ループが見やすく分かれているのですが、フォーラムのコードは融合していました。一見何をしているのか意味不明でした。