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: 2014-06-12 23:30:16

Got Ac..!! :D
my solution is on ****edit****
takes 2.53 sec....any suggession plz to optimise time....thanx in advance :)
--edit(Francky)--> Link removed

Last edit: 2014-06-13 07:10:56
[Lakshman]: 2014-05-05 19:14:14

Finally AC in 0.00!!!!!!

ivar.raknahs: 2014-04-19 16:50:43

any tricky case?
getting wrong answer again and again.
Got AC ;
using long costed me several WA.

Last edit: 2014-04-19 17:01:39
P_Quantum: 2013-12-20 09:28:59

Finally AC..!!

pm: 2013-08-26 11:00:33

easy..
:-)

Mukund Kumar: 2013-07-24 11:43:19

solving using trial division with precomputing...getting wa..can anyone provide some tricky case?however my solution gives these values
input
125478635856
130919894382
77145199750673
1000000000000000
0
output
2^4 3^1 7^1 1327^1 281423^1
2^1 3^1 179^1 121899343^1
328439^1 234884407^1
2^15 5^15
thanks in adv
My submission id is : 9710378
@tjandra: can u help?
Nevermind....got ac :)

Last edit: 2013-07-24 12:08:56
Vipul Pandey: 2013-07-18 17:00:58

easy one. ac in first attempt.

Chandan Singh: 2013-06-24 07:54:26

using pollard rho(python) getting TLE with trial division(C++) got AC ...

[Lakshman]: 2013-05-21 19:19:32

Trial Division is fine for this, No need to use Pollard Rho...

Last edit: 2013-05-22 06:43:30

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