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
indotech:
20180127 23:48:33
good problem to learn 

vishwanath_26:
20171012 14:23:45
Take care of output format......


stranger77:
20170207 10:56:49
Easy one AC in 1 go......0.0sec! 

aeonflux:
20161211 16:39:17
no need of sieve..simple brute force works!!!! 

Anuj Arora:
20160903 21:26:30
AC in one go!!! 111th question Last edit: 20160903 21:27:14 

vinay12345:
20160825 17:37:30
AC in one go ...0.00sec 

mkfeuhrer:
20160614 23:33:55
AC in 1 go :) my 100th :) prime funn..! 

AD:
20160614 21:35:46
Easy one ! Simple trial division will do. :D 

pranjalikumar9:
20160521 10:40:05
De Polignac's :) learnt something new!


sy_117:
20160405 23:50:26
wow such a nice ques nD i got AC in 0.0 sec !!!!! :P 
Added by:  Amlesh Jayakumar 
Date:  20120619 
Time limit:  0.197s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  DWITE Programming Contest 2012 (Own Problem) 