唯一分解定理
把n分解为 n=a1^p1*a2^p2*...的形式，易得每个ai^pi作为一个单独的整数最优。
坑：
n==1 ans=2；
n因子种数只有一个 ans++；
注意溢出。
#include <iostream>
#include <cstring>
using namespace std; typedef long long ll; ll ans=;
ll n;
ll sign[];
ll pri[];
int tot; void getpri (){
memset (sign,,sizeof sign);
sign[]=sign[]=;
for (int i=;i*i<;i++)
if (!sign[i])
for (int j=i*i;j<;j+=i)
sign[j]=;
tot=;
for (int i=;i<;i++)
if (!sign[i])
pri[tot++]=i;
} ll solved (){
if (n==)
return ;
ll ans=;
int flag=;
for (int i=;i<tot&&pri[i]*pri[i]<=n;i++){
ll temp=;
if (n%pri[i]==){
temp=;
flag++;
while (n%pri[i]==){
temp*=pri[i];
n/=pri[i];
}
}
ans+=temp;
}
if (n!=){
flag++;
ans+=n;
}
if (flag<=)
ans+=;
return ans;
} int main (){//int a=46341;cout<<a*a<<" "<<(1<<31)<<endl;
int kase=;
getpri ();
while (cin>>n&&n){
ans=solved ();
cout<<"Case "<<++kase<<": "<<ans<<endl;
}
return ;
}