欧拉函数最值

欧拉函数$\varphi(n)=$小于n且与n互质的正整数的数量。例如1、2、4、5、7、8与9互质，因此$\varphi(9)=6$。 与2互质的数是1，因此$\varphi(2)=1$，$2/\varphi(2)=2$。 与3互质的数是1、2，因此$\varphi(3)=2$，$3/\varphi(3)=1.5$。 与4互质的数是1、3，因此$\varphi(4)=2$，$4/\varphi(4)=2$。 与5互质的数是1、2、3、4，因此$\varphi(5)=4$，$5/\varphi(5)=1.25$。 与6互质的数是1、5，因此$\varphi(6)=2$，$6/\varphi(6)=3$。 与7互质的数是1、2、3、4、5、6，因此$\varphi(7)=6$，$7/\varphi(7)=1.1666\ldots$。 与8互质的数是1、3、5、7，因此$\varphi(8)=4$，$8/\varphi(8)=2$。 与9互质的数是1、2、4、5、7、8，因此$\varphi(9)=6$，$9/\varphi(9)=1.5$。 与10互质的数是1、3、7、9，因此$\varphi(10)=4$，$10/\varphi(10)=2.5$。 可以看出，对不超过10的n，当$n=6$时$n/\varphi(n)$取得最大值。 对不超过一百万的n，求使$n/\varphi(n)$取得最大值的n。

本题难度:

解答

若$p_1,\ldots,p_k$是$n$的全部素因子，则 $$\varphi(n)=n(1-\frac{1}{p_1})\ldots(1-\frac{1}{p_k}),$$ 因此欲令$n/\varphi(n)$最大，应当使$n$的素因子尽可能多，且每个素因子尽可能小，从而得 $$n=2\times 3\times 5\times 7\times 11 \times 13 \times 17=510510.$$ 本题无需编程。