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
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: | Jimmy |
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 |