Fundamental Theorem of Arithmetic states that any integer could be represented as product of one or more primes and such representation is unique, for example:
1000 = 2 * 2 * 2 * 5 * 5 * 5 1001 = 7 * 11 * 13 1002 = 2 * 3 * 167 1003 = 17 * 59 1009 = 1009
Here we regard
1009 as a singular case of product of only one prime value - itself!
It is still unknown whether factorization could be done efficiently, i.e. fast enough for big numbers. For example a
number built as product of two
200-digit primes (i.e. having only
400 digits itself) will require many thousand
years to decompose it back into original pair of primes on modern computers.
Of course this precious fact has great significance in cryptography. If fast algorithm is ever found, many crypting methods popular nowadays will become insecure at once! The classic example is an RSA algorithm of which you can learn more from the dedicated exercise and other linked tasks.
You will be given several numbers (not very large, so do not be afraid) to decompose them into products of primes.
Input data will contain amount of integers to factorize in the first line.
Next lines will contain one integer each (not exceeding
13 digits in length).
Answer should contain product representation for each of these integers, written like
p1 ... p3
are some primes sorted in non-decreasing order. Products should be separated with spaces.
input data: 5 1000 1001 1002 1003 1009 answer: 2*2*2*5*5*5 7*11*13 2*3*167 17*59 1009