FACT2 - Integer Factorization (29 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 29 digits.

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
2432902008176640000
77145199750673
0

Output:
317^1 9817^1
17^2 89^1 509^1
2^18 3^8 5^4 7^2 11^1 13^1 17^1 19^1
328439^1 234884407^1

hide comments
Howard Roark: 2017-10-22 17:48:10

Meeting the time constraints in a language like Java or python will be a real challenge. I have seen pure Java implementations of the quadratic sieve that can do it, but they represent a ton of code and years of effort. Pollard-rho is just a little bit too slow I think, not sure about lenstra's elliptic curve method variants.

[Lakshman]: 2017-02-10 20:21:48

Why java solutions are taking more time than earlier one. Even though Cluster has been upgraded to faster one.

[Lakshman]: 2015-12-08 04:42:46

Finally factored it.Used combination of Quadratic sieve + Fermat + Brent Pollard Rho.

Quadratic Sieve is enough for this.

Last edit: 2015-12-08 08:22:15
black MaMbA: 2014-08-27 15:01:07

is there any specific set of algorithms that we have to implement like lenstra elliptic curve,quadratic sieve because algorithms for first two versions of the problem get TLE in this version

numerix: 2009-10-10 21:27:08

It seems that algorithms usable for FACT1 do not help here. My Haskell FACT1 solution (AC in < 1 s) needs approx. 2 min (SPOJ time) to factor one(!) 30 digit number that is build of two large prime factors.

Last edit: 2009-10-14 14:01:57

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