HDU 4002 Find the maximum （歐拉函數

【題目大意】：

給出一個整數n，求一個數x，x在1到n之間，並且x/φ(x)最大(其中φ(x)為x的歐拉函數)。
【思路】：

則有：

要使f(x)最大，須使x含盡量多的不同素數因子。

代碼：

/*  
* Problem: HDU No.4002
* Running time: 1700MS  
* Complier: java  
* Author: javaherongwei 
* Create Time: 0:08 2015/9/23 星期三
*/  

import java.util.*;
import java.io.*;
import java.math.*;
import java.math.BigInteger;

public class Main
{
	public static void main(String args[])
	{
		Scanner cin = new Scanner(new BufferedInputStream(System.in));
		final int N=100005;
		boolean[] ok=new boolean[N];
		int [] prime= new int [N];
		int cnt=0;
		BigInteger [] fac= new BigInteger [65];
		for(int i=0; i0)
		{
	        n=cin.nextBigInteger();
		for(int i=1; i<=60; ++i)
			{
				 if(fac[i+1].compareTo(n)>0)
				 {
					 System.out.println(fac[i]);
					 break;
				 }
			}
		}
	}
}