1 // 高精度+搜索+质数 BZOJ1225 [HNOI2001] 求正整数
2 // 思路：
3 // http://blog.****.net/huzecong/article/details/8478689
4 // M=p1^(t1)*p2^(t2)*p3^(t3)....
5 // N=(t1+1)*(t2+1)*(t3+1)*(t4+1)...
6 // 所以t最大到16，就可以暴力搜索了
7
8
9 #include <bits/stdc++.h>
10 using namespace std;
11 #define LL long long
12 const double inf = 123456789012345.0;
13 const LL MOD =100000000LL;
14 const int N =1e5+10;
15 #define clc(a,b) memset(a,b,sizeof(a))
16 const double eps = 1e-7;
17 void fre(){freopen("in.txt","r",stdin);}
18 void freout() {freopen("out.txt","w",stdout);}
19 inline int read() {int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f;}
20
21 int n;
22 const int M=16;
23 const int p[16]= {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
24 double Log[16];
25 class bignum {
26 public:
27 LL num[N];
28 int tot;
29 bignum() {}
30 bignum(LL x) {
31 clear();
32 while (x) num[tot++] = x % MOD, x /= MOD;
33 }
34 void clear(){
35 tot = 0;
36 for (int i = 0; i < N; ++i) num[i] = 0LL;
37 }
38 void operator *= (const int &x){
39 for (int i = 0; i < tot; ++i) num[i] *= x;
40 for (int i = 0; i < tot; ++i)
41 if (num[i] >= MOD) {
42 num[i + 1] += num[i] / MOD;
43 num[i] %= MOD;
44 }
45 while (num[tot]) {
46 if (num[tot] >= MOD) {
47 num[tot + 1] += num[tot] / MOD;
48 num[tot] %= MOD;
49 }
50 ++tot;
51 }
52 }
53 void print() {
54 printf("%lld", num[tot - 1]);
55 for (int i = tot - 2; i >= 0; --i)
56 printf("%08lld", num[i]);
57 }
58 }ans(1);
59
60 int t[16],ct[16];
61 double mn;
62 int cnt;
63
64 void dfs(int d,int x,int m,double tem){
65 if(tem>mn) return;
66 if(x==1){
67 if(tem<mn){
68 mn=tem,cnt=d-1;
69 for(int i=1;i<d;i++) t[i]=ct[i];
70 }
71 }
72 for(int i=1;i*i<=x&&i<=m;i++){
73 if(!(x%i)){
74 if(i!=1){
75 ct[d]=i;
76 dfs(d+1,x/i,i,tem+(double)Log[d]*(i-1));
77 }
78 if(x/i<=m&&x/i!=i){
79 ct[d]=x/i;
80 dfs(d+1,i,x/i,tem+(double)Log[d]*(x/i-1));
81 }
82 }
83 }
84 }
85
86 int main(){
87 scanf("%d",&n);
88 for(int i=1;i<=15;i++) Log[i]=(double)log(p[i]);
89 mn=inf;
90 cnt=0;
91 dfs(1,n,n,0.0);
92 for(int i=1;i<=cnt;i++){
93 for(int j=t[i]-1;j>0;j--){
94 ans*=p[i];
95 }
96 }
97 ans.print();
98 return 0;
99 }
