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
nurbijoy:
20200518 16:26:26
I can't get how can I combine them. I solve FAC0 easily using basic factorization 

Scape:
20191228 09:41:22
@Lakshman, this is interesting. I tried different variations of brent pollard rho but was unable to pass. Then I modified my code to implement the pollard rho in exactly your way and got accepted in 1.87. If I optimize the pollard rho it gets TLE and with srand(time(0)), it also gets TLE.


mrmajumder:
20191127 07:21:33
Any hints for C++ about how to handle such a big number? 

[Lakshman]:
20180923 10:57:36
Surprised to see even my Brent RollardRho also got AC here. In my system, my code is unable to factor 29996186117636068716616424167 in given time don't how it got accepted here. 

liouzhou_101:
20180911 10:28:35
Why does my AC code for FACT1 using Brent Pollard Rho still get AC here? I thought it would get TLE instead. 

Howard Roark:
20171022 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. Pollardrho is just a little bit too slow I think, not sure about lenstra's elliptic curve method variants. 

[Lakshman]:
20170210 20:21:48
Why java solutions are taking more time than earlier one. Even though Cluster has been upgraded to faster one. 

[Lakshman]:
20151208 04:42:46
Finally factored it.Used combination of Quadratic sieve + Fermat + Brent Pollard Rho.


black MaMbA:
20140827 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:
20091010 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: 20091014 14:01:57 
Added by:  Jimmy 
Date:  20091008 
Time limit:  2.014s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL NODEJS PERL6 VB.NET 