FINDNUM - Tìm số
Tác giả: flashmt
Ngôn ngữ: C++
#include<iostream>
using namespace std;
int n,a[100],b[100],m,p[1000],np,aa[100],bb[100];
long long re;
void att(int m)
{
int i,j,k,q;
long long s=1;
q=0;
for (i=1;i<=m;i++)
{
aa[i]=a[i]; bb[i]=b[i];
}
for (i=1;i<m;i++)
for (j=i+1;j<=m;j++)
if (aa[i]>aa[j])
{
k=aa[i]; aa[i]=aa[j]; aa[j]=k;
k=bb[i]; bb[i]=bb[j]; bb[j]=k;
}
for (i=m;i>=1;i--)
if (s<re)
for (j=1;j<=bb[i];j++)
{
q++;
for (k=1;k<aa[i];k++)
{
s*=p[q];
if (s>=re) break;
}
if (s>=re) break;
}
if (s<re) re=s;
for (i=1;i<=m;i++)
for (j=i;j<=m;j++)
if (b[i]>0 && b[j]>0)
{
if (i==j && b[i]==1) continue;
b[i]--; b[j]--;
q=0;
for (k=1;k<=m;k++)
if (a[k]==a[i]*a[j])
{
q=k; break;
}
if (q)
{
b[q]++; att(m);
}
else
{
a[m+1]=a[i]*a[j]; b[m+1]=1;
att(m+1);
}
if (q) b[q]--;
else b[m+1]--;
b[i]++; b[j]++;
}
}
int main()
{
int i,j;
cin >> n;
m=0; np=0;
for (i=2;i<=n;i++)
{
if (n%i==0)
{
m++; a[m]=i;
while (n%i==0)
{
n/=i; b[m]++;
}
}
}
for (i=2;i<=1000;i++)
{
bool kt=true;
for (int j=2;j*j<=i;j++)
if (i%j==0)
{
kt=false; break;
}
if (kt)
{
np++; p[np]=i;
}
}
re=1000000000; re*=re;
att(m);
cout << re << endl;
return 0;
}