Problem 69

n/Φ(n)をnの素因数で表現すれば、どれが最大かは自明。

つまり、nの素因数を $p_1,p_2,￥ldots,p_n$ とするとき

$￥frac{n}{￥phi(n)}=￥left(￥frac{p_1}{p_1-1}￥cdot￥frac{p_2}{p_2-1}￥cdot￥cdot￥cdot￥frac{p_m}{p_m-1}￥right)$

import Number
main = print.last.takeWhile(<1000000).scanl1(*)$primes

コンテンツ