Project Euler 70

解答:https://ideone.com/IxvPb3

解法

 $\frac{n}{\varphi(n)}$が最小となる条件を考えると,$\varphi(n)=n-1$($n$は素数)なので,$n$が大きな素数であることが考えられます.しかし,このとき$n$と$\varphi(n)$で桁の置換はできません.
 $n$が2つの素数の積の場合を考えます.$n=p_1 \cdot p_2$で$\varphi(n)=(p_1 - 1)(p_2 - 1)$なので,$\frac{n}{\varphi(n)}$が十分小さく,かつ桁の置換ができる可能性はあります.実際,問題の例にある$n=87109$は2つの素数の積です.
 2つの素数の上限についてですが,$n<10^{7}$より,$p_1,p_2 < \sqrt{10^{7}}=3163$です.従って,その上限までの素数の中から2組選び,調べることで答えが求まります.私は素数リストの上限を多く見積もって4000にしました.