Project Euler 73（2）

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

分母dに対して、互いに素になる分子nを指定した範囲で数えればよいです。オイラーのφ関数を使うとだいたいφ(d) / 6になるのですが、その差分の計算を以前書きました。この計算はわざわざ素因数分解していますが、実際にはそこまではせずに直接φ関数を計算したほうが速いです。といっても実際には2割程度しか速くなりませんでした。