Find the maximum
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)
Problem Description
Euler's
Totient function, φ (n) [sometimes called the phi function], is used to
determine the number of numbers less than n which are relatively prime
to n . For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and
relatively prime to nine, φ(9)=6.
HG is the master of X Y. One day HG wants to teachers XY something about Euler's Totient function by a mathematic game. That is HG gives a positive integer N and XY tells his master the value of 2<=n<=N for which φ(n) is a maximum. Soon HG finds that this seems a little easy for XY who is a primer of Lupus, because XY gives the right answer very fast by a small program. So HG makes some changes. For this time XY will tells him the value of 2<=n<=N for which n/φ(n) is a maximum. This time XY meets some difficult because he has no enough knowledge to solve this problem. Now he needs your help.
HG is the master of X Y. One day HG wants to teachers XY something about Euler's Totient function by a mathematic game. That is HG gives a positive integer N and XY tells his master the value of 2<=n<=N for which φ(n) is a maximum. Soon HG finds that this seems a little easy for XY who is a primer of Lupus, because XY gives the right answer very fast by a small program. So HG makes some changes. For this time XY will tells him the value of 2<=n<=N for which n/φ(n) is a maximum. This time XY meets some difficult because he has no enough knowledge to solve this problem. Now he needs your help.
Input
There are T test cases (1<=T<=50000). For each test case, standard input contains a line with 2 ≤ n ≤ 10^100.
Output
For each test case there should be single line of output answering the question posed above.
Sample Input
2
10
100
Sample Output
6
30
Hint
If the maximum is achieved more than once, we might pick the smallest such n. Source
题意：给你一个n，找到n/phi(n)最大的一个数，如果多个输出最小的那个；
思路：
； 可得x/phi(x)=1/((1-1/p1)(1-1/p2).......(1-1/pn));
令p最多，且最小即是答案；
java码；
import java.util.*; import java.math.*; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); int[] a={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107 ,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331, 337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449, 457,461,463,467,479,487,491,499,503,509,521,523,541}; BigInteger[] ans=new BigInteger[110]; ans[0]=new BigInteger("1"); for(int i=1;i<=100;i++) ans[i]=ans[i-1].multiply(new BigInteger(""+a[i-1])); int T=cin.nextInt(); for(;T!=0;T--) { BigInteger n=cin.nextBigInteger(); for(int i=0;i<=100;i++) { if(ans[i].compareTo(n)>0) { System.out.println(ans[i-1]); break; } } } } }