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: p1^e1 * p2^e2 * ... * pk^ek where p1, p2, ..., pk are the distinct prime factors of the factorial of the given number in increasing order, and e1, e2, ..., ek are their exponents.

Example

Input:
10

Output:
2^8 * 3^4 * 5^2 * 7^1

hide comments
Deepak Singh Tomar: 2015-07-10 09:05:56

de polignac's :)

Devashish: 2015-06-26 09:22:05

My 50th! :) Nice problem and must try for factorisation and prime finding.

Dushyant Singh: 2015-06-19 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: 2015-06-18 12:02:04

accepted in 1 go!

Last edit: 2015-06-18 12:02:38
TUSHAR SINGHAL: 2015-06-10 16:34:28

awesome problem :-)

Madhav: 2015-02-12 13:59:09

done!

kbt: 2015-01-17 20:07:00

easy problem. a stupid syntactic error caused me one wa

re(vamsi): try this, this and this

Last edit: 2015-01-18 11:12:45
kbt: 2015-01-17 16:37:18

@bhargav parsi we should use the EOF concept
i.e we must read the input until EOF occurs.
try.. while(scanf("%d",&n)!=EOF){}

re(vamsi): no need to read till EOF, only one test case per test file

Last edit: 2015-01-18 11:08:12
Bhargav Parsi: 2015-01-17 15:14:58

no. of test cases is not mentioned?

re(vamsi): one test case per test file

Last edit: 2015-01-18 11:13:45
Adarsh kumar: 2014-12-03 05:47:30

Don't forget to give spaces in output format .. Costed me 3 WA ..
Also no need to check for N>10000 if you are doing it without sieves ..


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