Code: Select all
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <cctype>
#include <utility>
#include <cstdlib>
#include <algorithm>
#include <bitset>
using namespace std;
#define rep(i, b) for(i = 0; i < b; i++)
#define For(i, a, b) for( i = a; i <= b; i++)
#define N 1000000
#define NN 66000
#define PI acos( -1.0 )
#define INF 2147483646
#define LL long long
#define modu 100000007
bool mark[N + 5];
vector <int> primeList;
int min(LL a, LL b)
{
if(a < b) return a;
return b;
}
LL power(int x, int y)
{
LL pro = 1;
for(int i = y; i > 0; i--)
pro *= x;
return pro;
}
void mySieve()
{
int i, j;
memset(mark, true, sizeof(mark));
mark[0] = mark[1] = false;
for(i = 4; i <= N; i += 2) mark[i] = false;
for(i = 3; i * i <= N; i += 2)
{
if(mark[i])
{
for(j = i * i; j <= N; j += i)
mark[j] = false;
}
}
primeList.push_back(2);
for(i = 3; i < N; i += 2)
{
if(mark[i]) primeList.push_back(i);
}
// printf("%d\n", primeList.size());
//printf("%d \n", primeList[primeList.size() - 1]);
}
int main(void)
{
mySieve();
LL n;
int Case = 0;
while(scanf("%lld", &n) && n)
{
int i, j;
LL num = n;
i = 0;
LL sum = 0;
while(num != 1 && primeList[i] * primeList[i] <= num)
{
int count = 0;
while(num % primeList[i] == 0)
{
num /= primeList[i];
count++;
}
if(count != 0)
sum += power(primeList[i], count);
i++;
}
if(num == n || sum == n)
sum = n + 1;
else if(num != 1){
sum += num;
sum = min(n + 1, sum);
}
printf("Case %d: %lld\n", ++Case, sum);
}
return 0;
}