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
zephyr_96:
20180519 09:47:49
Precal using sieve will give TLE. Normal O(root(n)) works. : 

ameyanator:
20180401 22:16:52
Well if you know how to calculate the number of divisors of a number in sqrt(N) time then this is a easy question I guess 

jayharsh:
20170815 16:06:15
you will get TLE in brute force but optimize it and your code will work 

raichu7:
20170727 00:28:37
TLE>AC :) 

abudraya:
20170723 21:04:04
nice one problem 

nahid_007:
20170519 07:54:30
easy problem.. go through divisor count by using prime factorization


manas0008:
20160312 18:14:42
Trial division method have been given ac.


minhthai:
20160120 11:07:26
you can ac with bruteforce in java :) 

Vishal:
20151017 09:25:07
week test cases 

i_am_looser:
20150526 09:17:34
Used optimized sieve ........... Got accepted ........... I think polard rho is for FACT1 ............. 
Added by:  Duc 
Date:  20091008 
Time limit:  1.138s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL NODEJS PERL6 VB.NET 