オイラーのphi関数 in ぷろぐらむ

http://www.prefield.com/algorithm/math/euler_phi.html
最近Project Eulerでお世話になっているphi関数について。ちょと感激したので思わず。

phi(n) = n * (1 - 1/p1) * ... * (1 - 1/pn) (pi (1<=i<=n)はnを素因数分解したもの)

な訳ですが、小さい方の素数から

n -= n / pi
(この後nを割り切れなくなるまでpiで割る)

とすると、計算上は

n *= 1 - 1/pi

となるわけで、綺麗だなーと思いました。以上日記。