题目大意，对于一个数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。

接下来上代码：

 

#include
      
       #include
       
        #include
        
         #include
         
          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;}