The 36th ACM/ICPC Asia Regional Dalian Site —— Online Contest Find the maximum

  
http://acm.hdu.edu.cn/showproblem.php?pid=4002

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. 
 

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
题意是：给你一个N,2 <= n <=N，求n/φ(n)最大时n的值。
分析：φ(n)=n(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pk)欧拉函数:对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。
n/φ(n)=(p1/(p1-1))(p2/(p2-1))(p3/(p3-1))(p4/(p4-1))......(pk/(pk-1));
因此素数因子越多n/φ(n)越大，特别注意：要保证素因子积小于N。
java：
import java.math.*;
import java.util.*;
public class Main{public static void main(String[]args){Scanner in=new Scanner(System.in);int num=1000;boolean[] b=new boolean[num+1];long[] bb=new long[num];for(int i=0;i<num;i++) b[i]=true;for(int i=2;i*i<num+1;i++)for(int j=i*i;j<num+1;j+=i)b[j]=false;int k=0;for(int i=1;i<num+1;i++) if(b[i]) bb[k++]=i;//素数打表int n=in.nextInt();BigInteger N;while(n--!=0){   BigInteger m=BigInteger.ONE;N=in.nextBigInteger();for(int i=0;m.compareTo(N)==-1;i++){  if(m.multiply(BigInteger.valueOf(bb[i])).compareTo(N)>0) break;m=m.multiply(BigInteger.valueOf(bb[i]));}System.out.println(m);}}}