Project Euler : Problem 12 ～ 三角数の約数の数 (2) - ツムジのひとりごとちょっと間が空きましたが、Problem 12 の続きです。 問題はこちらをご覧ください。 実際の解法を示す前に、前提となる条件をいくつか挙げておきます。 n 番目の三角数は Tn = n * (n + 1) / 2 で表せる。 隣り合う正の整数 n と n + 1 は「互いに素」である。ここで、n が偶数の場合は n / 2 と n + 1 が、n が奇数の場合は n と (n + 1) / 2 がそれぞれ「互いに素」となる。 正の整数 x の約数の数を f(x) とすると、a と b が「互いに素」であれば、f(a * b) = f(a) * f(b) となる。 以上のことより、n が偶数の場合は f(Tn) = f(n / 2) * f(n + 1) となり、n が奇数の場合は f(Tn) = f(n) * f((n + 1) / 2) となる。 ここで、f(Tn) を小さい方から見
