UVa 10856 - Recover Factorial

// UVa 10856 - Recover Factorial

#include <iostream>
#include <string.h>
#include <vector>
#include <math.h>
#include <stdio.h>
using namespace std;

#define integer long long int
#define MaxX 2703664

bool isprime[MaxX + 1];
integer n;
integer T[MaxX + 1], P[MaxX + 1], F[MaxX + 1];

unsigned long long find(unsigned long long ini, integer fin) {
	if (ini >= fin)
		return ini;
	unsigned long long mid = ((ini + fin) >> 1);
	if (n <= T[mid])
		return find(ini, mid);
	else
		return find(mid + 1, fin);
}

int main() {
	memset(isprime, true, sizeof(isprime));
	for (int i = 4; i <= MaxX; i += 2) {
		isprime[i] = false;
		F[i] = 2;
	}

	vector<integer> prime;
	prime.push_back(2);
	for (int i = 3; i <= 1830; i += 2)
		if (isprime[i]) {
			for (int j = i * i; j <= MaxX; j += (i << 1)) {
				isprime[j] = false;
				F[j] = i;
			}
			prime.push_back(i);
		}

	T[0] = 0;
	T[1] = 0;
	P[0] = 0;
	P[1] = 0;

	n = 0;
	integer x;
	for (x = 2; T[x - 1] <= 10000001; x++) {
		if (isprime[x])
			P[x] = 1;
		else {
			P[x] = P[x / F[x]] + 1;
		}
		T[x] = T[x - 1] + P[x];
	}

	int t = 0;
	while ((cin >> n) && n >= 0) {
		t++;
		unsigned long long pos = find(0, MaxX);
		if (T[pos] == n)
			printf("Case %d: %llu!\n", t, pos);
		else
			printf("Case %d: Not possible.\n", t);
	}
	return 0;
}