PTIME  Prime Time
For your math homework this week your teacher gave you five large numbers and asked you to find their prime factors. However these numbers aren't nearly large enough for someone with knowledge of programming like yourself. So you decide to take the factorial of each of these numbers. Recall that N! (N factorial) is the product of the integers from 1 through N (inclusive). It’s your job now to create a program to help you do your homework.
Input
Each test case contains a number N (2 ≤ N ≤ 10000).
Output
The output should contain a line representing the prime factorization of the factorial given number, which should be of the form: p_{1}^e_{1} * p_{2}^e_{2} * ... * p_{k}^e_{k} where p_{1}, p_{2}, ..., p_{k} are the distinct prime factors of the factorial of the given number in increasing order, and e_{1}, e_{2}, ..., e_{k} are their exponents.
Example
Input: 10 Output: 2^8 * 3^4 * 5^2 * 7^1
hide comments
Deepak Singh Tomar:
20150710 09:05:56
de polignac's :) 

Devashish:
20150626 09:22:05
My 50th! :) Nice problem and must try for factorisation and prime finding. 

Dushyant Singh:
20150619 14:15:17
Got 3 RE then i read Kid Algorist's comment. Thanks Kid Algorist. :) I think limit of N is upto 10007 and as some comments say you don't have to read till EOF i.e. there is only one input. However EOF program will also give AC. 

jaikishan:
20150618 12:02:04
accepted in 1 go! Last edit: 20150618 12:02:38 

TUSHAR SINGHAL:
20150610 16:34:28
awesome problem :) 

Madhav:
20150212 13:59:09
done! 

kbt:
20150117 20:07:00
easy problem. a stupid syntactic error caused me one wa


kbt:
20150117 16:37:18
@bhargav parsi we should use the EOF concept


Bhargav Parsi:
20150117 15:14:58
no. of test cases is not mentioned?


Adarsh kumar:
20141203 05:47:30
Don't forget to give spaces in output format .. Costed me 3 WA ..

Added by:  Amlesh Jayakumar 
Date:  20120619 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  DWITE Programming Contest 2012 (Own Problem) 