UVa 583 - Prime Factors

// UVa 583 - Prime Factors

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

#define maxn 46342
#define datatype signed long long int

bool isprime[maxn];
datatype prime[maxn];

int main() {
	datatype m = 1;
	prime[0] = 2;
	memset(isprime, true, sizeof(isprime));
	for (datatype i = 4; i < maxn; i += 2)
		isprime[i] = false;
	for (datatype i = 3; i < maxn; i++) {
		if (isprime[i]) {
			datatype j = i * i;
			while (j < maxn) {
				isprime[j] = false;
				j += (i << 1);
			}
			prime[m++] = i;
		}
	}

	datatype g;
	while (cin >> g && g != 0) {
		printf("%lld = ", g);
		if (g < 0) {
			printf("-1 x ");
			g = -g;
		}
		datatype sqrtg = sqrt(g);
		bool first = true;
		for (datatype i = 0; i < m && prime[i] <= sqrtg; i++) {
			while (g % prime[i] == 0) {
				if (!first)
					printf(" x ");
				else
					first = false;
				printf("%lld", prime[i]);
				g /= prime[i];
			}
		}
		if (g != 1) {
			if (!first)
				printf(" x ");
			else
				first = false;
			printf("%lld", g);
		}
		printf("\n");
	}
	return 0;
}