---

Problem 69

---

Totient Maximum

Euler’s Totient function, $\phi (n)$ [sometimes called the phi function], is used to determine the number of numbers less than $n$ which are relatively prime to $n$. For example, as $1$, $2$, $4$, $5$, $7$, and $8$, are all less than nine and relatively prime to nine, $\phi (9)=6$.

$n$	Relatively Prime	$\phi (n)$	$n/\phi (n)$
$2$	$1$	$1$	$2$
$3$	$1,2$	$2$	$1.5$
$4$	$1,3$	$2$	$2$
$5$	$1,2,3,4$	$4$	$1.25$
$6$	$1,5$	$2$	$3$
$7$	$1,2,3,4,5,6$	$6$	$1.1666\dots$
$8$	$1,3,5,7$	$4$	$2$
$9$	$1,2,4,5,7,8$	$6$	$1.5$
$10$	$1,3,7,9$	$4$	$2.5$

It can be seen that $n=6$ produces a maximum $n/\phi (n)$ for $n\le 10$.

Find the value of $n\le 1,000,000$ for which $n/\phi (n)$ is a maximum.

---

欧拉总计函数与最大值

小于$n$且与$n$互质的正整数的数量记为欧拉总计函数$\phi (n)$。例如，$1$、$2$、$4$、$5$、$7$和$8$均小于$9$且与$9$互质，因此$\phi (9)=6$。

$n$	互质的数	$\phi (n)$	$n/\phi (n)$
$2$	$1$	$1$	$2$
$3$	$1,2$	$2$	$1.5$
$4$	$1,3$	$2$	$2$
$5$	$1,2,3,4$	$4$	$1.25$
$6$	$1,5$	$2$	$3$
$7$	$1,2,3,4,5,6$	$6$	$1.1666\dots$
$8$	$1,3,5,7$	$4$	$2$
$9$	$1,2,4,5,7,8$	$6$	$1.5$
$10$	$1,3,7,9$	$4$	$2.5$

可以看出，对于$n\le 10$，当$n=6$时$n/\phi (n)$取得最大值。

对于$n\le 1,000,000$，求使得$n/\phi (n)$取得最大值的$n$。

---