http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1732
题目大意，对于一个数N（1 ~ 2147483647），存在两个或两个以上的数的LCM = N，求这些数的最小和。
看到题目第一时间想到了质因数分解，感觉可以从这个方向来做，首先先验证下思路是否正确；
假设有k个数，a1，a2， .... ak，其中gcd( am, an ) = d != 1，其余的数 gcd 均为1，那么lcm1 = a1 * a2 * .... * ak / d，sum1 = a1 + a2 + .... + ak，如果将其中的 am 用 am / d 取代，那么lcm2 = lcm1， 但sum2 < sum1。由此可知，如果这 k 个数中不互质的数越多，sum 就会越大。
所以当这 k 个数互质的时候，sum会取到最小值。想要这 k 个数是互质的，就可以直接对 N 进行质因数分解就行了。
接下来考虑用素数筛来对质因数分解进行优化，考虑到如果直接筛出 2147483647 以内的素数不太容易，但是可以用一个方法来优化，一个数如果不能被它开根号以内的数整除，那么它就是质数。如果 N 是大于sqrt（2147483647），且一直没找到质因数，那么就一定是素数了，保险起见，我们直接筛出50000以内的所有素数。
①对于一个质数，那么直接考虑 1 和 N，所以答案就是 N + 1；
②对于一个质数的k次方，例如4，只有一个互质的因数的，++ans；
接下来就是一些要注意的小细节了，例如 2^31 - 1 是一个质数。对于1，要输出2。
接下来上代码：
#define _CRT_SECURE_NO_WARNINGS
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int MAXN = 50000;
const int MAXP = 64 + 5;
int N, p, x;
int numPrime;
long long ans;
int vis[MAXN];
int prime[MAXN / 6];
//素数筛筛素数，vis[质数] = false;
void sieve(int n)
{
int m = (int)sqrt(n + 0.5);
memset(vis, false, sizeof(vis));
for(int i = 2; i <= m; ++ i)
if(vis[i] == false)
for(int j = i * i; j <= n; j += i)
vis[j] = true;
}
void init()
{
sieve(MAXN);
numPrime = -1;
for(int i = 2; i < MAXN; ++ i)
if(vis[i] == false)
prime[++numPrime] = i;
}
int main()
{
init();
int tCase = 0;
while(scanf("%d", &N) && N)
{
int n = N;
ans = x = 0;
for(int i = 0; n > 1 && i <= numPrime; ++ i)
if(n % prime[i] == 0)
{
n /= prime[i];
p = prime[i];
while(n % prime[i] == 0)
{
n /= prime[i];
p *= prime[i];
}
//互质因数个数++
++x;
ans += p;
}
//只有一个因数或者 N = 1
if(x == 1 || N == 1)
++ans;
//大于49999的质数，或者 N = 1，注意2147483647是质数
if(N == n)
ans = N + 1LL;
printf("Case %d: %lld\n", ++ tCase, ans);
}
return 0;
}