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
Mitch Schwartz:
20120622 01:53:32
Writing "while (std::cin >> foo)" is just a different way to read until End Of File.


Amlesh Jayakumar:
20120621 23:18:23
There's only one N per testcase as indicated. I'm not sure why you need to read till eof (my program didn't and AC'd).


Rishi Mukherje:
20120621 22:27:44
for python users: there are some extra whitespace lines which may create problem. 

Jared Deckard:
20120621 22:27:44
Got TLE when expecting 1 number...


devu:
20120621 22:27:44
@Amlesh:Just clarify the question to all the users that they need to read it till end of file and test case can be 1 or 5 or anything


:D:
20120621 22:27:44
Yes, I also read until EOF, but description is unclear.


xxx:
20120621 22:27:44
Got AC !!!! gud prob ....:) 

Amlesh Jayakumar:
20120621 22:27:44
@Devendra Please look at the constraints again.


Amlesh Jayakumar:
20120621 22:27:44
There's only one N per testcase as indicated. 

Surya:
20120621 22:27:44
Yeah! Read till EOF..else you'll get 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) 