FACT0  Integer Factorization (15 digits)
This is a problem to test the robustness of your Integer Factorization algorithm.
Given some integers, you need to factor them into product of prime numbers.
The largest integer given in the input file has 15 digits. FACT1 is a harder version of this problem (the numbers are larger).
You may need to use a general factorization algorithm since no special numbers (e.g. Fermat numbers) are considered when designing the input data.
Input
There are several numbers given, each one in a line.
The input ends with a number 0.
The number of test cases is about 10.
Output
For each number, print in a line the factorization of it. See examples below for the output format.
Example
Input: 3111989 13091989 77145199750673 0 Output: 317^1 9817^1 17^2 89^1 509^1 328439^1 234884407^1
hide comments
karan:
20150330 17:05:13
finally ac :') 

Takanori MAEHARA:
20150217 23:35:51
What should be the output for 1?


Dhawal Harkawat:
20141114 12:59:19
very poor form of output to be given, costed me many WA's. Finally AC. 

Kid Algorist:
20141009 02:13:49
For all those getting TLE


Yassine Fadhlaoui:
20140925 00:58:32
Last edit: 20140925 01:01:55 

Luc:
20140821 19:56:15
Got TLE because using %I64u... really annoying that it doesn't cause an error, just TLE.


Anmol Pandey:
20140720 16:35:02
Can anybody point out why am i getting TLE


`Ak:
20140628 15:43:17
http://ideone.com/isG0H2


TIGM:
20140628 10:27:18
got accepted with worst time 4.13 sec


[Lakshman]:
20140613 04:57:06
@Mayur Shingote First remove the link.

Added by:  Jimmy 
Date:  20091008 
Time limit:  1.138s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL NODEJS PERL6 VB.NET 