Find the maximum
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 2081    Accepted Submission(s): 875

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
Hint
If the maximum is achieved more than once, we might pick the smallest such n.
 

Source
The 36th ACM/ICPC Asia Regional Dalian Site —— Online Contest 

思路：
给出一个整数n，求一个数x，x在1到n之间，并且x/φ(x)最大(其中φ(x)为x的欧拉函数)。
由欧拉函数为积性函数，即：如果
则有：

且：


则有：


要使f(x)最大，须使x含尽量多的不同素数因子。

因为数的范围给的很大，所以需要用高精度来做；并且因为数据量很大，所以一般都要通过打表来找到规律。

代码：
打表代码： 
<span style="font-weight: normal;">#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include <cmath>  
  
const int maxn = 1000;  
int vis[100000];  
int prime[maxn];  
int ans[maxn][maxn];  


void prime_table(int n)  
{  
    int m = sqrt(n+0.5);  
    memset(vis,0,sizeof(vis));  
    for(int i = 2;i <= m;i++)  
    {  
        if(!vis[i])  
        {  
            for(int j = i*i;j <= n;j += i)  
            {  
                vis[j] = 1;  
            }  
        }  
    }  
    for(int i = 1,j = 0;i <= n;i++)  
    {  
        if(vis[i] == 0)  
        {  
            prime[j++] = i;  
        }  
    }  
}  
//大整数乘法  
void multiply(int a[],int n)  
{  
    int vis = 0;  
    for(int i = 0;i <= maxn;i++)  
    {  
        vis += a[i] * n;  
        a[i] = vis % 10;  
        vis /= 10;  
    }  
}  
  
void table(int n)  
{  
    ans[0][0] = 2;  
    prime_table(500);  
    for(int i = 1;i <= n;i++)  
    {  
        memcpy(ans[i],ans[i-1],maxn*sizeof(int));  
        multiply(ans[i],prime[i+1]);  
    }  
}  
  
int main ()  
{  
    freopen("in.txt","r",stdin);  
    table(100);  
    for(int i = 0;i <= 52;i++)  
    {  
        int j;  
        for(j = 100;j >= 0;j--)  
            if(ans[i][j] != 0)break;  
        if(j >= 0)  
            printf("\"");  
        for(;j >= 0;j--)  
            printf("%d",ans[i][j]);  
        printf("\",\n");  
    }  
    return 0;  
}  </span>
题AC代码： 
#include <cstdio>  
#include <cmath>  
#include <cstdlib>  
#include <cstring>  
#include <iostream>  
#include <algorithm>  
using namespace std;  
  
char tb[][150] = {  
"2",  
"6",  
"30",  
"210",  
"2310",  
"30030",  
"510510",  
"9699690",  
"223092870",  
"6469693230",  
"200560490130",  
"7420738134810",  
"304250263527210",  
"13082761331670030",  
"614889782588491410",  
"32589158477190044730",  
"1922760350154212639070",  
"117288381359406970983270",  
"7858321551080267055879090",  
"557940830126698960967415390",  
"40729680599249024150621323470",  
"3217644767340672907899084554130",  
"267064515689275851355624017992790",  
"23768741896345550770650537601358310",  
"2305567963945518424753102147331756070",  
"232862364358497360900063316880507363070",  
"23984823528925228172706521638692258396210",  
"2566376117594999414479597815340071648394470",  
"279734996817854936178276161872067809674997230",  
"31610054640417607788145206291543662493274686990",  
"4014476939333036189094441199026045136645885247730",  
"525896479052627740771371797072411912900610967452630",  
"72047817630210000485677936198920432067383702541010310",  
"10014646650599190067509233131649940057366334653200433090",  
"1492182350939279320058875736615841068547583863326864530410",  
"225319534991831177328890236228992001350685163362356544091910",  
"35375166993717494840635767087951744212057570647889977422429870",  
"5766152219975951659023630035336134306565384015606066319856068810",  
"962947420735983927056946215901134429196419130606213075415963491270",  
"166589903787325219380851695350896256250980509594874862046961683989710",  
"29819592777931214269172453467810429868925511217482600306406141434158090",  
"5397346292805549782720214077673687806275517530364350655459511599582614290",  
"1030893141925860008499560888835674370998623848299590975192766715520279329390",  
"198962376391690981640415251545285153602734402721821058212203976095413910572270",  
"39195588149163123383161804554421175259738677336198748467804183290796540382737190",  
"7799922041683461553249199106329813876687996789903550945093032474868511536164700810",  
"1645783550795210387735581011435590727981167322669649249414629852197255934130751870910",  
"367009731827331916465034565550136732339800312955331782619462457039988073311157667212930",  
"83311209124804345037562846379881038241134671040860314654617977748077292641632790457335110",  
"19078266889580195013601891820992757757219839668357012055907516904309700014933909014729740190",  
"4445236185272185438169240794291312557432222642727183809026451438704160103479600800432029464270",  
"1062411448280052319722448549835623701226301211611796930357321893850294264731624591303255041960530",  
"256041159035492609053110100510385311995538591998443060216114576417920917800321526504084465112487730",  
"64266330917908644872330635228106713310880186591609208114244758680898150367880703152525200743234420230"  
};  
  
int main()  
{
    //freopen("in.txt","r",stdin);  
    char str[150];  
    int t;  
    cin>>t;  
    while(t--){  
        scanf("%s",str);   
        int i=0;
		int str1= strlen(str); 
        while ( str1 > strlen(tb[ i ]) )  
            ++ i;  
        if ( strlen(tb[ i ]) == str1 && strcmp( tb[ i ], str ) > 0 )  
            -- i;  
        if ( strlen(tb[ i ]) > str1 )  
            -- i;  
        if ( str1 == 1 && strcmp( str, "6" ) >= 0 )  
            printf("6\n");  
        else if ( str1 == 1 && strcmp( str, "2" ) >= 0 )  
            printf("2\n");  
        else  
            printf("%s\n",tb[ i ]);  
    }  
    return 0;  
}