要令n尽量小 则当p1<p2<p3<...<pn时 有t1>=t2>=t3>=..>=tn(由此可见 pn肯定小于2、3、5、7...53等16个质数)
然后对tn进行dfs 求出大于n的序列 选出代表整数最小的(比较方法 用对数性质 log a^k = k log a 取对数再比)
最后高精度乘法...这里我写崩很多次 高精度写得很丑........
代码:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int n,m,s[16]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53},a[16],ans[16];
double minss,s1;
long long pr[10000];
void judge()
{
s1=0;
for (int q=0;q<16;q++)
{
s1+=log(s[q])*double (a[q]);
if (s1>minss) return ;
}
if (s1<minss) {
minss=s1;
for (int q=0;q<16;q++)
ans[q]=a[q];
}
}
int l=0;
void out(int l)
{
printf("%d",pr[l]);
for (int q=l-1;q>=0;q--)
printf("%04d",pr[q]);
}
void print(int *ans)
{
pr[0]=1;
for (int q=0;q<16;q++)
for (int p=0;p<ans[q];p++)
{
for (int t=0;t<=l;t++)
pr[t]*=s[q];
for (int t=0;t<l;t++)
{
pr[t+1]+=pr[t]/10000;
pr[t]%=10000;
}
while (pr[l]/10000)
{
pr[l+1]+=pr[l]/10000;
pr[l]%=10000;
l++;
}
}
out(l);
int p2=1;
for (int q=0;q<16;q++) p2*=ans[q]+1;
printf(" %d",p2);
}
void dfs(int i,int k)
{
if (k>=n)
{
judge();
return ;
}
if (a[i-1]==0) return ;
for (int q=0;q<=a[i-1];q++)
{
a[i]=q;
dfs(i+1,k*(q+1));
a[i]=0;
if (k*(q+1)>=n) break;
}
}
int main()
{
scanf("%d",&n);
ans[0]=n-1;
minss=double((n-1))*log(2);
for (int q=0;q<n-1;q++)
{
a[0]=q;
dfs(1,q+1);
}
print(ans);
//system("pause");
return 0;
}