題目大意
給定一個整數(shù)n，求一個最小的整數(shù)m≤n欲低，使得\frac{m}{\phi (m)}最小辕宏。
n≤10^{25000}，最多有100組數(shù)據(jù)砾莱。
思路
設(shè)m的質(zhì)因數(shù)分解為m= \prod _{i=1}^{k} p_{i}^{c_i}
則\phi (m) = m \prod _{i=1}^{k} \frac{p_i - 1}{p_i}
\frac{m}{\phi (m)}=\prod _{i=1}^{k} \frac {p_i-1}{pi}
可以看出當(dāng)p_i越小時瑞筐，\frac {p_i-1}{pi}越大。
因此我們只需篩出一部分素數(shù)腊瑟，然后乘到n為止聚假。
大概只需要求出[1,60000]的素數(shù)即可。
程序太丑就不放出來了闰非。
