欧拉函数\(\varphi(n)\)计算小于\(n\)的自然数中和\(n\)互质的数的个数，比如1, 2, 4, 5, 7和8都小于9并且和9素质，因此\(\varphi(9)=6\)。下表列示了小于等于十的数的欧拉函数值：
可以看到对于\(n\le10\)当\(n=6\)时\(n/\varphi(n)\)取得最大值，求对于\(n\le1,000,000\)，在\(n\)等于多少时\(n/\varphi(n)\)取得最大值？
分析：欧拉函数是数论中经常会遇到的一个函数，我们可以通过一个公式将它和数\(n\)的质因数连接起来。一般地，对于正整数\(n\)，设\(p|n\)表示所有整除\(n\)的质数，实际上就是\(n\)的质因数，则我们有：
\[
{\displaystyle \varphi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right),}
\]
如对于\(\varphi(36)\)，可以如下计算：
\[
{\displaystyle \varphi (36)=\varphi \left(2^{2}3^{2}\right)=36\left(1-{\tfrac {1}{2}}\right)\left(1-{\tfrac {1}{3}}\right)=36\cdot {\tfrac {1}{2}}\cdot {\tfrac {2}{3}}=12.}
\]
因此，题目中要求\(n/\varphi(n)\)的最大值，则有：
\[
n/\varphi(n)=\frac{n}{n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)}=\frac{1}{\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)}=\prod\limits_{p|n}\dfrac{p}{p-1}
\]
因为\(p/(p-1)>1\)，则要使\(n/\varphi(n)\)最大，只需要使得求出对于\(n\le10^6\)中质因数最多的数即可。我们可以通过从小到大把质数依次相乘，保证其乘积不超过一百万，但再乘一个质数就会超过一百万。经过尝试，我们发现这个数是\(2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17=510510\)，即为题目所求。显然，这道题只需要笔算即可，不过我还是写了一段小代码，如下：
# time cost = 6.91 ms ± 154 μs
from sympy import prime
def main(N=10**6):
i,prod,arr = 1,1,[]
while prod <= N:
prod *= prime(i)
arr.append(prod)
i += 1
return arr[-2]Project Euler 69: Totient maximum
原文：https://www.cnblogs.com/metaquant/p/11958828.html