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

/*
 * Wheel factorization using a 480-spoke wheel, covering 2310 numbers.
 * Factors < 13 are treated independently.
 */

const unsigned int wheel[] = {
	12, 4, 2, 4, 6, 2, 6, 4, 2, 4,
	6, 6, 2, 6, 4, 2, 6, 4, 6, 8,
	4, 2, 4, 2, 4, 14, 4, 6, 2, 10,
	2, 6, 6, 4, 2, 4, 6, 2, 10, 2,
	4, 2, 12, 10, 2, 4, 2, 4, 6, 2,
	6, 4, 6, 6, 6, 2, 6, 4, 2, 6,
	4, 6, 8, 4, 2, 4, 6, 8, 6, 10,
	2, 4, 6, 2, 6, 6, 4, 2, 4, 6,
	2, 6, 4, 2, 6, 10, 2, 10, 2, 4,
	2, 4, 6, 8, 4, 2, 4, 12, 2, 6,
	4, 2, 6, 4, 6, 12, 2, 4, 2, 4,
	8, 6, 4, 6, 2, 4, 6, 2, 6, 10,
	2, 4, 6, 2, 6, 4, 2, 4, 2, 10,
	2, 10, 2, 4, 6, 6, 2, 6, 6, 4,
	6, 6, 2, 6, 4, 2, 6, 4, 6, 8,
	4, 2, 6, 4, 8, 6, 4, 6, 2, 4,
	6, 8, 6, 4, 2, 10, 2, 6, 4, 2,
	4, 2, 10, 2, 10, 2, 4, 2, 4, 8,
	6, 4, 2, 4, 6, 6, 2, 6, 4, 8,
	4, 6, 8, 4, 2, 4, 2, 4, 8, 6,
	4, 6, 6, 6, 2, 6, 6, 4, 2, 4,
	6, 2, 6, 4, 2, 4, 2, 10, 2, 10,
	2, 6, 4, 6, 2, 6, 4, 2, 4, 6,
	6, 8, 4, 2, 6, 10, 8, 4, 2, 4,
	2, 4, 8, 10, 6, 2, 4, 8, 6, 6,
	4, 2, 4, 6, 2, 6, 4, 6, 2, 10,
	2, 10, 2, 4, 2, 4, 6, 2, 6, 4,
	2, 4, 6, 6, 2, 6, 6, 6, 4, 6,
	8, 4, 2, 4, 2, 4, 8, 6, 4, 8,
	4, 6, 2, 6, 6, 4, 2, 4, 6, 8,
	4, 2, 4, 2, 10, 2, 10, 2, 4, 2,
	4, 6, 2, 10, 2, 4, 6, 8, 6, 4,
	2, 6, 4, 6, 8, 4, 6, 2, 4, 8,
	6, 4, 6, 2, 4, 6, 2, 6, 6, 4,
	6, 6, 2, 6, 6, 4, 2, 10, 2, 10,
	2, 4, 2, 4, 6, 2, 6, 4, 2, 10,
	6, 2, 6, 4, 2, 6, 4, 6, 8, 4,
	2, 4, 2, 12, 6, 4, 6, 2, 4, 6,
	2, 12, 4, 2, 4, 8, 6, 4, 2, 4,
	2, 10, 2, 10, 6, 2, 4, 6, 2, 6,
	4, 2, 4, 6, 6, 2, 6, 4, 2, 10,
	6, 8, 6, 4, 2, 4, 8, 6, 4, 6,
	2, 4, 6, 2, 6, 6, 6, 4, 6, 2,
	6, 4, 2, 4, 2, 10, 12, 2, 4, 2,
	10, 2, 6, 4, 2, 4, 6, 6, 2, 10,
	2, 6, 4, 14, 4, 2, 4, 2, 4, 8,
	6, 4, 6, 2, 4, 6, 2, 6, 6, 4,
	2, 4, 6, 2, 6, 4, 2, 4, 12, 2
};

const unsigned int initial[] = { 2, 3, 5, 7, 11 };

int main(int argc, char** argv) {
	unsigned long long input;

	if (argc < 2) {
		fprintf(stderr, "Usage: %s <number>\n", argv[0]);
		return EXIT_FAILURE;
	}
	input = strtoull(argv[1], NULL, 10);

	printf("%llu:", input);
	{
		const unsigned int *p = initial;
		while (p < initial + sizeof(initial) / sizeof(unsigned int)) {
			while (input % *p == 0) {
				printf(" %u", *p);
				input /= *p;
			}
			p++;
		}
	}

	/*
	 * Start by testing 13, on the second spoke of the wheel.
	 */
	{
		unsigned long long test = 13;
		const unsigned int *spoke = wheel + 1;
		const unsigned int *wheel_end = wheel + 480;

		/* Keep track of maximum possible divisor */
		unsigned long long div;
		do {
			/* Factor test out of input */
			div = input / test;
			while (div * test == input) {
				printf(" %llu", test);
				input = div;
				div = input / test;
			}

			/*
			 * At this point, test can no longer divide input. Since
			 * div = floor(input / test), any remaining factors must be
			 * between test and div.
			 */

			test += *spoke;
			if (++spoke == wheel_end)
				spoke = wheel;
		} while (test <= div);
	}

	if (input != 1)
		printf(" %llu", input);
	printf("\n");

	return EXIT_SUCCESS;
}