FACT1  Integer Factorization (20 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 20 digits. FACT2 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 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
minhnguyent546:
20220814 06:04:18
20 digits is larger than ULLONG_MAX


cjn2007:
20220112 03:09:46
use __int128 in c++14! 

ashish_2495:
20200617 16:31:26
you should use unsigned long long int


shammya:
20191119 03:47:31
which data type should i use in c++ to store 20 digit integer !!!.Anyone help ... 

selfcoder24:
20190629 06:39:53
@paulmcvn Can u check my code? 

selfcoder24:
20190626 19:51:19
My brent fails for 1111111111111 and i am getting TLE. Please help 

cake_is_a_lie:
20170403 21:46:27
Well, Brent's method will pass, albeit slowly. 

Sarthak Munshi:
20150907 18:54:35
Pollard Rho Brent Integer Factorization ! 

Duc:
20091008 14:20:38
There are inputs which are products of two large primes 
Added by:  Jimmy 
Date:  20091008 
Time limit:  3.065s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL NODEJS PERL6 VB.NET 