Find the maximum
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 1990 Accepted Submission(s): 837
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
10
100
Sample Output
6
30
30
Hint
If the maximum is achieved more than once, we might pick the smallest such n.
Source
题解：先算出来前100个数；找规律；由于数太大，用java；
代码：
import java.math.BigInteger;
import java.util.Scanner; public class Main {
static int vis[] = new int[];
static int p[] = new int[];
static BigInteger a[] = new BigInteger[];
static void getp()
{
for(int i = ; i < ; i++)
vis[i] = ;
vis[] = ;
for(int i = ; i <= ; i++)
{
if(vis[i] == )
for(int j = i * i; j <= ; j += i)
{
vis[j] = ;
}
}
int tp = ;
for(int i = ; i <= ; i++)
{
if(vis[i] == )
p[tp++] = i;
}
}
public static void main(String[] args){
Scanner cin = new Scanner(System.in);
getp();
a[]=BigInteger.valueOf();
for(int i=;i<=;i++)
{
a[i] = a[i-].multiply(BigInteger.valueOf(p[i-]));
}
int t = cin.nextInt();
while(t-- > )
{
BigInteger x;
x = cin.nextBigInteger();
// for(int i = 0; i <= 10; i++){
// System.out.println(a[i]);
// }
if(x.compareTo(BigInteger.valueOf()) < ){
System.out.println("");
continue;
}
for(int i=;i<=;i++)
{
if(a[i].equals(x)){
System.out.println(a[i]);
break;
}
else if(a[i].compareTo(x) > )
{
System.out.println(a[i-]);
break;
}
}
}
}
}