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
Kid Algorist:
20141106 13:55:45
Limit is beyond 10000.


ivar.raknahs:
20141006 21:30:01
learned a new thing!


arun vinud:
20140821 21:35:12
Very nice and easy problem :) 

Anurag Mandilwar:
20140807 14:23:14
Good problem!! 

Gautam Kumar:
20140219 20:12:06
@Amlesh Jayakumar


heatOn:
20140216 10:25:08
Strange , using long long int for all variables gives AC in 0 seconds but using int gives AC in 0.1. Last edit: 20140216 10:30:05 

hiddenman:
20140215 15:39:06
good 1..... :) 

pika_pika:
20131231 16:37:53
don't consider the limit as 10000. I used a dynamic limit of the input to run the code and sieve. AC now. and no need of EOF 

Manu Narsaria:
20131228 05:43:14
nyc problem...


Blue Moon:
20131227 17:59:44
Enjoyed doing it!!

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) 