杭电4002 亚洲区预赛大连赛区

这道题先是用数学公式可以推出来一个式子，接下来就是大数，，，碰到好几次大数了，以前都是用c或c++写的，这道题用c或c++实在是太麻烦，于是一咬牙，一跺脚，硬着头皮看起了Java，上午看了一点，下午问了问xd一些基本语法，于是便开始写了，既借助网上代码，又不断的问xd，终于ac了，这叫一个不容易啊，，用Java写的第一道题啊，，，，接下来再练一下Java，把nyoj上的大数题用Java再做一遍。。。。。。题目：

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

ac代码：

import java.util.*;
import java.math.BigInteger;
public class Main {

	/**
	 * @param args
	 */
	public static boolean pri(int n){
		
		for(int i=2;i<=(int)Math.sqrt(n);++i)
		{
			if(n%i==0)
			  return false;
		}
		return true;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		
		BigInteger aa[]=new BigInteger[110];
	    int j=0,tt;
		int bb[]=new int[110];
		Scanner cin=new Scanner(System.in);
		for(int i=2;j<110;++i)
		{
			if(pri(i))
			{ bb[j++]=i;}
		}
		aa[1]=new BigInteger("6");
		BigInteger b6=new BigInteger("6");
		//BigInteger b2=new BigInteger("2");
		for(int i=2;i<105;++i)
		{
			aa[i]=new BigInteger(""+bb[i]).multiply(aa[i-1]);
			
		}
		BigInteger n;
		tt=cin.nextInt();
		while(tt-->0)
		{
		    n=cin.nextBigInteger();
		    if(n.compareTo(b6)<0)
		    {
		    	if(n.compareTo(BigInteger.ONE)==0)
		    		System.out.println("1");
		    	
		    	else System.out.println("2");
		    }
		    else if(n.compareTo(b6)==0)
		    	System.out.println("6");
		    else{
			    for(int i=1;i<102;++i)
			    {
			    	if(n.compareTo(aa[i])<=0)
			    	{
			    		System.out.println(aa[i-1]);
			    		break;
			    		
			    	}
			    }
		    	
			}
		}
	}

}