#include <iostream>
#include <math.h>
#include <fstream>
#include <vector>
using namespace std;
#define N_MAXPRIMES 10000000
#define N_MAXFACTORS 128

bool is_prime(long long n, vector<signed int> primes);
int main(int argc, char *argv[]) {
	long long n = strtoll(argv[1], NULL, 10);
	cout << "Received " <<n<<".\n";
	vector<signed int> primes;
	primes.resize(N_MAXPRIMES);
	int factors[N_MAXFACTORS];
	ifstream Primes("primes_up_to_10m.txt");
	int i;
	int temp;
	for(i=0;i<=N_MAXPRIMES;i++) {
		Primes >> primes[i];
		//cout << temp << endl;
	}
	i=2;
	/*while(i<=N_MAXPRIMES) {
		cout << primes[i] << endl;
		i++;
	
	}*/
	long long sqrtn = (long long) sqrt(n)+1;
	int factnum = 0;

	while(i<=sqrtn) {
		if((n % i) == 0) {
			factors[factnum] = i;
			vector<signed int>* c;
			if(n > N_MAXPRIMES) {*c=primes;}else{*c=0;}
			if(!(is_prime((n / i), c))) {
				n = n/i;
				i=2;
				sqrtn = (long long) sqrt(n)+1;
			} else {
				factors[++factnum] = n/i;

				break;
			}
				
			factnum++;
		}else{i++;}
	
	}
	i=0;
	if(factnum != 0) {
		cout << n <<": ";
		for(i=0;i<=factnum;i++) {
			cout << factors[i] << " ";
		}cout << endl;
	} else {
		cout << n << ": is prime." << endl;
	}

	
	return 1;
}
bool is_prime(long long n, vector<signed int>* primes = 0) {
	long sqrtn = (long) sqrt(n)+1;
	int i;
	cout << "In is_prime("<<n<<")..." << endl;

	if(n > N_MAXPRIMES) {
		for(i=2;i<=sqrtn;i++) {
			if(n % i == 0) {
				return false;
			}
		}
		return true;
	} else {

		for(i=2;primes[i] <= sqrtn;i++) {
			if(n % primes[i] == 0) {
				return false;
			}
		}
		return true;
	}
}