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
Mitch Schwartz: 2012-06-22 01:53:32

Writing "while (std::cin >> foo)" is just a different way to read until End Of File.

std::istream::operator>> returns the original object, which is converted to boolean via std::ios::operator void*, which returns null pointer (false) if and only if failbit or badbit is set. Reaching End Of File when more data is expected sets eofbit and failbit.

scanf returns EOF (a macro defined in stdio.h) on reaching End Of File.

Please consider Jared's and zukow's suggestions to make the problem statement clearer, as right now we must rely on the comments to understand it properly.

Amlesh Jayakumar: 2012-06-21 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).

EDIT: I notice that the submissions that got AC while looking till EOF all use scanf() as opposed to cin. I used cin (that probably is it).

Last edit: 2012-06-21 23:22:34
Rishi Mukherje: 2012-06-21 22:27:44

for python users: there are some extra whitespace lines which may create problem.

Jared Deckard: 2012-06-21 22:27:44

Got TLE when expecting 1 number...
Each LINE contains a number N.

devu: 2012-06-21 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: 2012-06-21 22:27:44

Yes, I also read until EOF, but description is unclear.

Input should be something like:
"Input contains some lines. Each with exactly one number N (2<=N<=10000)."

And for output:
"For each test case ..."

test case != input file

Last edit: 2012-06-20 06:48:57
xxx: 2012-06-21 22:27:44

Got AC !!!! gud prob ....:)

Amlesh Jayakumar: 2012-06-21 22:27:44

@Devendra- Please look at the constraints again.
@Gaurav- I'm not too sure what's wrong either :S. Looks right from my end (I'll look into it a bit more later on).

Last edit: 2012-06-19 21:41:46
Amlesh Jayakumar: 2012-06-21 22:27:44

There's only one N per testcase as indicated.

Surya: 2012-06-21 22:27:44

Yeah! Read till EOF..else you'll get WA..


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)