本文主要是介绍例题10-4 UVa10791 Minimum Sum LCM（最小公倍数的最小和），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
看白书
要点：
运用唯一分解定理，使每个ai^pi作为一个单独的整数时最优。例如72=8*9时最优。注意：如果本身是一个素数最后还要+1，而且如果本身分解后只有一种因子，最后也要+1，如1=1*1，答案是2。一开始我担心时间想用线性筛什么的，后来发现做不出，看了一下题解发现只要普通的遍除即可，现在做题因为担心时间有点畏手畏脚了啊，其实一般的题上去莽就可以了。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>int main()
{int n,cnt,m;int kase = 1;long long sum;while (scanf("%d", &n) && n){sum = 0;cnt = 0;m = sqrt(n+0.5);printf("Case %d: ", kase++);for (int i = 2; i <= m; i++){if (n%i == 0){cnt++; //注意这里cnt只有最开始+1，否则对后面判断有影响long long temp = i;n /= i;while (n%i == 0)//看能不能再除i{n /= i;temp *= i;}sum += temp;}}if (n != 1 || cnt == 0)//最后剩下一个素数或本身为素数{cnt++;sum += n;}if (cnt == 1) //像1，8这种只有一种因子的最后还要+1sum++;printf("%lld\n", sum);}return 0;
}这篇关于例题10-4 UVa10791 Minimum Sum LCM（最小公倍数的最小和）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
