オイラーの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
となるわけで、綺麗だなーと思いました。以上日記。