Hàm phi Euler và hoán vị

Time limit: 1.0s , Memory limit: 500M , Points: 20 (partial)

REF: Project Euler

Hàm phi Euler, ký hiệu $\phi (n)$ ~\phi (n)~ được tính bằng số các số nguyên từ $1$ ~1~ đến $n$ ~n~ mà nguyên tố cùng nhau với $n$ ~n~. Ví dụ $\phi (9) = 6$ ~\phi (9) = 6~ gồm các số $1, 2, 4, 5, 7, 8$ ~1, 2, 4, 5, 7, 8~.

Số $1$ ~1~ được coi là nguyên tố cùng nhau với bất kỳ số nguyên dương nào nên $\phi (1) = 1$ ~\phi (1) = 1~.

Xét $\phi (87109) = 79180$ ~\phi (87109) = 79180~ và nhận thấy rằng $87109$ ~87109~ là một hoán vị của $79180$ ~79180~.

Hãy lập trình tìm $x$ ~x~ thỏa $1 < x < n$ ~1 < x < n~ mà $\phi (x)$ ~\phi (x)~ là một hoán vị của $x$ ~x~ và tỷ lệ $\frac{x}{\phi (x)}$ ~\frac{x}{\phi (x)}~ là nhỏ nhất.