uva 10791 - Minimum Sum LCM(分解因数）

uva 10791 - Minimum Sum LCM(分解因子）

题目大意：uva 10791 - Minimum Sum LCM

题目大意：给出一个n，将n分解成n = p1 ^ k1 * p2 ^ k2 * ... * pm ^ km，然后求解sum = ∑(1≤i≤m)pi ^ ki.

解题思路：比较费解的是n本身就是素数，那么n应该分解成n^ 1 + 1 ^ 1,所以sum= n + 1，还有一种就是n = p ^ k，sum = p ^ k + 1.

#include <stdio.h>
#include <math.h>

int main () {
	int cas = 1, n;
	while (scanf("%d", &n), n) {
		long long sum = 0, tmp = sqrt(n), cnt = 0;
		for (int i = 2; i <= tmp; i++) {
			if (n % i == 0) {
				int c = 1;
				cnt++;
				while (n % i == 0) {
					c *= i;
					n /= i;
				}
				sum += c;
			}
		}

		if (n > 1 || cnt == 0) {
			sum += n;
			cnt++;
		}
		if (cnt == 1)	sum++;

		printf("Case %d: %lld\n", cas++, sum);
	}
	return 0;
}