248 Numbers for which Euler’s totient function equals 13!

Problem 248 – Project Euler

phi(n) = 13 ! となる n を探す問題．

一見，探索範囲が広そうに見えるが…

n を 素因数ベースで考えれば，そもそも n に含まれる素因数が少ないことに気づく．

m , n を互いに素として， phi(m * n) = q ならば， phi(n) = q / phi(m)．で，q が小くなる．

ということで， n の素因数を固定して，問題を小くして再帰的に解いた．

Haskellのコード(パスは答えの下10桁，the 100,000th such number）

http://firestorage.jp/download/78b8ef8964240964e88d2fd78e535c8799aa6782