滦平住房和城乡建设厅网站,win7 网站建设,国内个人网站建设,企业策划文案论文我们可以先用唯一分解定理将这个数字分解成素因子幂的乘积#xff0c;为了得到最小的和#xff0c;我们可以发现#xff1a;每个 素因子的幂单独分开的和是最小的。
先说明每个素因子都是以出现的最大的次数出现。因为最小公倍数一定#xff0c;因此至少有一个数字的这个素…我们可以先用唯一分解定理将这个数字分解成素因子幂的乘积为了得到最小的和我们可以发现每个 素因子的幂单独分开的和是最小的。
先说明每个素因子都是以出现的最大的次数出现。因为最小公倍数一定因此至少有一个数字的这个素因子的幂等于最大的次数如果不一次取完另一个和其他的因子的乘积肯定没有1和其他因子的乘积小。
再说明每个素因子都是分开的每个素因子的幂都是大于2的都分开的话相当于每个素因子的幂都乘1而不分开的话对于那两个素因子都乘了一个不小于2 的数字因此分开更小。
剩下的素数也要加入到答案里面。
#includecstdio
#includecstring
#includealgorithm
#includeclimits
#includecctype
#includequeue
#includeset
#includecmathusing namespace std;typedef long long ll;
const int INF0x3f3f3f3f;
const int MAXN1e55;
bool check[MAXN];
int prime[MAXN];
ll cnt[MAXN];
int tot;
ll n;void creat_prime()
{tot0;for(int i2;iMAXN;i){if(!check[i]) prime[tot]i;for(int j0;jtot prime[j]*iMAXN ;j){check[prime[j]*i]true;if(i%prime[j]0) break;}}
}int main()
{creat_prime();int t;int Case0;while(~scanf(%lld,n) n){Case; t0;ll ans0;printf(Case %d:,Case);if(n1){printf( %d\n,2);continue;}for(int i0;itot;i){cnt[i]1;while(n%prime[i]0){cnt[i]*prime[i];n/prime[i];}if(cnt[i]1){anscnt[i];t;}if(n1)break;}if(n1){ansn; t;}if(t1) ans;printf( %lld\n,ans);}
}
