SPOJ.com - Problem FACTCG2

FACTCG2 - Medium Factorization

no tags

The task in this problem is to write a number in a multiplication of prime numbers separated by “ x ”. You need to put the number 1 in this multiplication.

Input

The input consists of several lines.

Each line consists of one integer N (1 ≤ N ≤ 10⁷) .

Output

For each line you need to output the factorization separated by “ x ” and including 1.

Sample

Input
1
2
4
8

Output
1
1 x 2
1 x 2 x 2
1 x 2 x 2 x 2

Submit solution!

hide comments

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

	Abhishek Mishra: 2012-06-23 17:47:50 Edit:code link removed by saurabh8c please see notes before posting comments here is my solution link Last edit: 2012-12-19 03:50:48
	Abhishek Mishra: 2012-06-23 17:39:46 hey please tell me about output specifications.. i am getting wa
	jaans: 2012-06-21 11:23:02 phewwww!!!!!!!!finally after 4 pages of tle.. got AC ;) 0(n) sieve works but with a little optimization ;) Last edit: 2012-06-21 16:13:50
	Aman Verma: 2012-05-20 09:54:02 is the sieve of erasthanes oworkin fine here or we have to switch to sieve of arkin
	Aman Verma: 2012-05-20 09:51:39 for the input write while(cin num) { } and when the user press ctrl+z the input taking process will end
	mAddy: 2012-04-28 07:42:40 any reason for runtime error ?? my code is working fine for sample input but it gives me SIGSEGV when i submit!!
	sankicoder: 2012-04-09 12:58:08 seive or segmented seive is to be used./.??? RE: O(n) sieve works fine here. Last edit: 2012-05-09 19:34:49
	Satyanarayan patel: 2012-03-30 20:37:41 hey how the input file end..............???
	Alex Anderson: 2012-03-17 22:11:05 Using O(sqrt(N)) algorithm... If I print the output, TLE. If I don't print the output, WA. RE: that's because O(sqrt(N)) algorithm isn't fast enough, and precalculation actually helps. You can try the eratosthen's O(n) sieve first,and you'll get accepted. Last edit: 2012-03-20 15:46:02
	Sanchit Abrol: 2012-03-10 21:57:40 @:D I think there are thousands, only then a O(sqrt(N)) solution can time out.

Submit solution!

Added by:	Phyllipe Medeiros
Date:	2012-02-26
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64