对于一个数n 设它有两个不是互质的因子a和b 即lcm（a，b） = n 且gcd为a和b的最大公约数
则n = a/gcd * b；
因为a/gcd 与 b 的最大公约数也是n
且 a/gcd + b < a + b
又因为a/gcd 与 b 互质 所以n的最小的因子和为 所有质因子的和
同理推广到多个质因子
由算术基本定理求出所有的质因子
则 nut = 所有质因子 ^ 个数 的和 自己想一想为什么把。。。
注意n为1时
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = , INF = 0x7fffffff;
LL primes[maxn], vis[maxn];
int ans;
void init()
{
mem(vis, );
ans = ;
for(int i=; i<maxn; i++)
if(!vis[i])
{
primes[ans++] = i;
for(LL j=(LL)i*i; j<maxn; j+=i)
vis[j] = ;
}
} LL qpow(LL a, LL b)
{
LL res = ;
while(b)
{
if(b & ) res = res * a;
a = a * a;
b >>= ;
}
return res;
} int main()
{
LL n;
init();
int kase = ;
while(cin>> n && n)
{
LL temp = n;
LL nut = ;
int cnt = ;
for(int i=; i<ans && primes[i]*primes[i] <= n; i++)
{
LL cnt2 = ;
while(n % primes[i] == )
{
n /= primes[i];
cnt2 *= primes[i];
}
if(cnt2 > )
{
nut += cnt2;
}
}
if(n > )
{
nut += n;
}
if(nut == temp)
nut++;
if(temp == )
nut += ;
printf("Case %d: %lld\n",++kase, nut); } return ;
}