本文主要是介绍uva10791 - Minimum Sum LCM，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
分析摘以为大神的：：思路很清晰
分解质因子的一个题，将最小公倍数分解质因子，最小的和sum便为各个质因子的相应次方数之和。
此题难点在于几个特殊的情况的处理：
（1）当N = 1时，应输出2（1*1=1,sum=1+1=2）；（2）当N是素数的时候，输出N+1（N*1=N,sum=N+1）；
（3）当只有单质因子时，sum=质因子相应次方+1；
（4）当N=2147483647时，它是一个素数，此时输出2147483648，但是它超过int范围，应考虑用long long。代码如下：
#include <cstdio>
#include <cmath>
#include <cstring>
#define M 100010
bool prime[M];
void is_prime()
{int len = sqrt(M+0.5);memset(prime,0,sizeof(prime));for(int i = 2; i <= len; i++) if(prime[i]==0)for(int j = i*i; j < M; j+=i) prime[j] = 1;
}
int judge(int n)
{if(n<M) return !prime[n];int len = sqrt(n+0.5);for(int i = 2; i <= len; i++)if(n%i==0) return 0;return 1;
}
int main()
{int n, cas = 0;is_prime();while(scanf("%d",&n),n){printf("Case %d: ",++cas);if(judge(n)) { printf("%lld\n",(long long)n+1); continue;}int len = (int)sqrt(n+0.5), num = 0, tt;long long ans = 0;for(int i = 2; i <= len; i++){if(n%i) continue;num++;tt = 1;while(n%i==0){tt*=i;n/=i;}ans+=tt;}if(num==1||n!=1) ans+=n;printf("%lld\n",ans);}return 0;
}
这篇关于uva10791 - Minimum Sum LCM的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
