欧拉函数\(\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]