我們可以先用唯一分解定理將這個數字分解成素因子冪的乘積，為了得到最小的和，我們可以發現：每個 素因子的冪單獨分開的和是最小的。

先說明每個素因子都是以出現的最大的次數出現。因為最小公倍數一定，因此至少有一個數字的這個素因子的冪等于最大的次數，如果不一次取完，另一個和其他的因子的乘積肯定沒有1和其他因子的乘積小。

再說明每個素因子都是分開的：每個素因子的冪都是大于2的，都分開的話相當于每個素因子的冪都乘1，而不分開的話對于那兩個素因子都乘了一個不小于2 的數字，因此分開更小。

剩下的素數也要加入到答案里面。

#include<cstdio> #include<cstring> #include<algorithm> #include<climits> #include<cctype> #include<queue> #include<set> #include<cmath>using namespace std;typedef long long ll; const int INF=0x3f3f3f3f; const int MAXN=1e5+5; bool check[MAXN]; int prime[MAXN]; ll cnt[MAXN]; int tot; ll n;void creat_prime() {tot=0;for(int i=2;i<MAXN;i++){if(!check[i]) prime[tot++]=i;for(int j=0;j<tot && prime[j]*i<MAXN ;j++){check[prime[j]*i]=true;if(i%prime[j]==0) break;}} }int main() {creat_prime();int t;int Case=0;while(~scanf("%lld",&n) && n){Case++; t=0;ll ans=0;printf("Case %d:",Case);if(n==1){printf(" %d\n",2);continue;}for(int i=0;i<tot;i++){cnt[i]=1;while(n%prime[i]==0){cnt[i]*=prime[i];n/=prime[i];}if(cnt[i]>1){ans+=cnt[i];t++;}if(n==1)break;}if(n>1){ans+=n; t++;}if(t==1) ans++;printf(" %lld\n",ans);} }

總結

以上是生活随笔為你收集整理的UVa10791的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。