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
excursionist:
20140612 23:30:16
Got Ac..!! :D


[Lakshman]:
20140505 19:14:14
Finally AC in 0.00!!!!!! 

ivar.raknahs:
20140419 16:50:43
any tricky case?


P_Quantum:
20131220 09:28:59
Finally AC..!! 

pm:
20130826 11:00:33
easy..


Mukund Kumar:
20130724 11:43:19
solving using trial division with precomputing...getting wa..can anyone provide some tricky case?however my solution gives these values


Vipul Pandey:
20130718 17:00:58
easy one. ac in first attempt. 

Chandan Singh:
20130624 07:54:26
using pollard rho(python) getting TLE with trial division(C++) got AC ... 

[Lakshman]:
20130521 19:19:32
Trial Division is fine for this, No need to use Pollard Rho... Last edit: 20130522 06:43:30 
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 