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.
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 77145199750673 0 Output: 317^1 9817^1 17^2 89^1 509^1 328439^1 234884407^1
hide comments
sankalp_7:
20210625 11:59:03
Nice observation for the question>


alpha_power:
20210320 14:00:14
TLE will come for overflow!!! 

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


deerawat:
20201229 12:47:51
Easy one 

smap:
20201008 09:30:35
Spoj will give you TLE if integer overflow occurs.


chandan_5362:
20200702 10:41:10
I am getting TLE for this problem even after using sieve method in PYTHON3.


adikrmishra_1:
20200617 17:24:16
just use factorization in sqrt(n) time :)


lm10_piyush:
20191121 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).


zarif_2002:
20191102 09:04:02
Just do basic sieve before approaching. that's it. 

drdrunkenstein:
20190823 20:42:08
Python 3 gets tle for trial division 
Added by:  Jimmy 
Date:  20091008 
Time limit:  1.138s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL NODEJS PERL6 VB.NET 