#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

void Factorization(long long num, _Bool SieveArray[])
{
	long long div = 2, to_facotrize = num;

	printf("Prime factorization of %lli:\n", num);
	while (div < to_facotrize)
	{
		if (SieveArray[div] == 1) 
		{
			if (to_facotrize % div == 0)
			{

				printf("%lli x ", div);
				to_facotrize /= div;
			} 

			else {
				if ( div == 2 ) div = 3;
				else div += 2;
			}
		} else {
			div += 2;
		}
	}
	printf("%lli\n", div);
}

int main(int argc, char const *argv[])
{
	clock_t start, end;
	start = clock();
	void Factorization(long long num, _Bool SieveArray[]);

	// Sieve of Eratosthenes 
	long long n = 1000001, i, j;
	long long sqrt_n = sqrt(n);

	_Bool SieveArray[n];
	SieveArray[0] = 0, SieveArray[1] = 0;

	for (i = 2; i < n; i++)
		SieveArray[i] = 1;

	for (i = 2; i < sqrt_n; i++)
		if (SieveArray[i])
			for (j = i*i; j < n; j+=i)
				SieveArray[j] = 0;


	long long num;
	while( 1 ) 
	{
		if (scanf("%lld", &num) != 1) {
			fprintf(stderr, "Error: Undefined stdin!\n");
			return 100;
		} else {
			if ( num == 1 ) {
				printf("Prime factorization of 1:\n1\n");
			} else if ( num < 0 ) {
				fprintf(stderr, "Error: Undefined stdin!\n");
				return 100;
			} else if ( num == 0 ) {
				break;
			} else if ( num < 1000001 ) {
				if (SieveArray[num] == 1) {
					printf("Prime factorization of %lli:\n%lli\n", num, num);
				} else {
					Factorization(num, SieveArray);
				}	
			} else {
				Factorization(num, SieveArray);
			}
		}
	}

	end = clock();
	double time_taken = ((double) (end - start)) / CLOCKS_PER_SEC;
	printf("It's took %f seconds to execute\n", time_taken);

	return 0;
}