SPOJ.com - Problem PTIME

PTIME - Prime Time

#math #number-theory

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₁^e₁ * p₂^e₂ * ... * p_k^e_k where p₁, p₂, ... p_k are the distinct prime factors of the factorial of the given number in increasing order, and e₁, e₂, ... e_k are their exponents.

Example

Input:
10

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

Submit solution!

hide comments

< Previous 1 2 3 4 5 6 7 8 9 Next >

	Snehasish Roy ;): 2012-07-15 10:00:04 there are many problems of this type.. test cases are also weak ... Why this has not been moved to tutorial yet?? Move this to tutorial.... :@ or improve the test cases.... Last edit: 2012-07-19 18:57:50
	Aditya Pande: 2012-07-11 09:51:16 plz tell me why submission ID 7297845 got WA i tried quite a lot of test cases myself Last edit: 2012-07-11 09:55:49
	saket diwakar: 2012-07-03 18:16:50 enjoyed to code it...:) Last edit: 2012-07-03 18:21:35
	Amlesh Jayakumar: 2012-06-24 04:22:37 @Saurabh- As mentioned in the problem, all test cases contain a value N that is <= 10^4.
	Saurabh Jain: 2012-06-23 07:33:14 @Amlesh: the value of n is greater than 10^4..you should have corrected it..cost me 5 WAs !!
	Mitch Schwartz: 2012-06-23 01:16:08 @Amlesh: Your response doesn't make sense, but I'll drop it. People can always read comments or guess about input format.
	Amlesh Jayakumar: 2012-06-22 20:48:54 @Mitch- Seeing as there are AC solutions that don't input until EOF, I'll keep the problem as is for now. @Swayam- I see incorrect outputs for certain tests. Keep testing (keep in mind that N <= 10^4)
	napster: 2012-06-22 07:37:56 AC,no need to check for EOF.
	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

Submit solution!

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)