FACT0 - Integer Factorization (15 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 15 digits. FACT1 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
328439^1 234884407^1

hide comments
nowshadsub15: 2022-05-29 20:43:51

$Does latext work in spoj$

Last edit: 2022-05-29 20:44:07
mars_coder: 2021-11-04 15:58:20

Trial division.............

sankalp_7: 2021-06-25 11:59:03

Nice observation for the question->
For any number N, there is at most 1 prime factor of N from sqrt(N) to N.

alpha_power: 2021-03-20 14:00:14

TLE will come for overflow!!!

deepak_prem: 2021-01-27 16:24:39

for those who use sieve, just take the size of array 3 * (10^7) then you get an ac.

deerawat: 2020-12-29 12:47:51

Easy one

smap: 2020-10-08 09:30:35

Spoj will give you TLE if integer overflow occurs.
Do the trial division, but take care of integer overflow in your (( for )) loop.

Last edit: 2020-10-08 09:31:02
chandan_5362: 2020-07-02 10:41:10

I am getting TLE for this problem even after using sieve method in PYTHON3.
Any suggestions!!!

adikrmishra_1: 2020-06-17 17:24:16

just use factorization in sqrt(n) time :)
for help :)

lm10_piyush: 2019-11-21 16:37:12

I have tried sieve with prime integer factorization but it gives me WA, anyone suggests any issue, I've test my code on many test cases it works fine.. largest number is 999999999999999 (9 15times).

Last edit: 2019-11-21 16:41:57

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