http://projecteuler.net/index.php?section=problems&id=73
既約の分数の個数を求めるには、条件を満たす全ての分数の個数から既約でない分数の個数を引けばいいです。分母と分子の最大公約数が2で割り切れる分数は、分母が12以下とすると、
2/12 2/10 2/8 4/12 2/6 4/10 2/4 4/8 6/12 …
これは分母分子を2で割ると、
1/6 1/5 1/4 1/3 2/5 1/2 2/4 3/6 …
分母が6以下の分数に対応しています。最大公約数が3で割り切れる分数なども考えられますが、9で割り切れる分数は3で割り切れる分数に含まれるので、べき乗項がある場合は考えなくてもよいです。また2で割り切れる分数と3で割り切れる分数は、6で割り切れる分数をどちらも含みます。包除原理ですね。また、分母が最小の分数は2/5なので、12000/5までを考えればよいです。
これを実装すると前回より5倍ほど速くなりました。
