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.


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.


For each number, print in a line the factorization of it. See examples below for the output format.



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
ashish_2495: 2020-06-17 16:31:26

you should use unsigned long long int

shammya: 2019-11-19 03:47:31

which data type should i use in c++ to store 20 digit integer !!!.Anyone help ...

selfcoder24: 2019-06-29 06:39:53

@paulmcvn Can u check my code?

selfcoder24: 2019-06-26 19:51:19

My brent fails for 1111111111111 and i am getting TLE. Please help

cake_is_a_lie: 2017-04-03 21:46:27

Well, Brent's method will pass, albeit slowly.

rahulpadhy: 2016-11-30 07:44:48

Last edit: 2016-12-04 06:10:29
Sarthak Munshi: 2015-09-07 18:54:35

Pollard Rho Brent Integer Factorization !

Duc: 2009-10-08 14:20:38

There are inputs which are products of two large primes

Added by:Jimmy
Time limit:3.065s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL NODEJS PERL6 VB.NET