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
jayharsh: 2017-08-15 16:06:15

you will get TLE in brute force but optimize it and your code will work

raichu7: 2017-07-27 00:28:37

TLE-->AC :)

abudraya: 2017-07-23 21:04:04

nice one problem

nahid_007: 2017-05-19 07:54:30

easy problem.. go through divisor count by using prime factorization

manas0008: 2016-03-12 18:14:42

Trial division method have been given ac.
test case of 993960000099397 gave me tle on ideone but got accepted here.weak test cases.

minhthai: 2016-01-20 11:07:26

you can ac with bruteforce in java :)

Vishal: 2015-10-17 09:25:07

week test cases

i_am_looser: 2015-05-26 09:17:34

Used optimized sieve ........... Got accepted ........... I think polard rho is for FACT1 .............

Rishab Banerjee: 2015-04-11 15:28:49

no need for seive or polard-rho just use simple brute force also if 993960000099397 10 times gives tle dont worry your code still might work

Lehar: 2015-04-07 16:40:46

For those getting TLE using sieve(naive way), try using bitwise sieve.


Added by:Duc
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