69 Totient Maximum

Problem 69

欧拉函数 $\phi(n)$（有时也成为 $\phi$ 函数）表示与 $n$ 互斥且小于 $n$ 的数的个数。比如 1,2,4,5,7,8 这几个数与 9 互斥，所有 $\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...
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\leq 10$，$n=6$ 时 $n/\phi(n)$ 最大。

求 $n\leq 1 000 000$ 时，$n$ 为何值时 $n/\phi(n)$ 最大。

如果遍历 $n$，对于每一个 $n$，求 $\phi(n)$，是 $O(n^2\lg n)$ 的复杂度，其中 $n^2$ 是两层对 $n$ 的循环，内部使用欧几里得算法计算是否互斥 $\lg n$，这个是理论上限，实际会低很多。不过即使是 $O(n^2)$，因为 $n$ 比较大，也不太现实。

直观地想，想要 $n/\phi(n)$ 大，那么 $\phi(n)$ 就要小，也就是说，互斥的数越少越好，如果一个数，其质因数的次数都为 1，那么互斥的数比较少。那就要求这个数包含的质因数越多越好。依次对每个质数相乘，小于 1000000 的乘积是 510510。

考虑 $n=510510$ 附近的某个 $n$，因为没有质因数 17，那么 17 的若干倍与这个数就互斥，但是不与 510510 互斥，其他质因数类似。