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^7) .

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 11 Next >

	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.
	:D: 2012-03-10 12:22:34 What does "several" means. Because it seems to mean at very least hundreds.
	Santiago Palacio: 2012-03-07 14:14:48 @Namandeep 10^7 miller rabin is slower than making a sieve.
	Naman: 2012-03-07 13:54:12 am making a boolean array for all integers till 10^7 and checking for their primality , using miller rabin, TLE :(
	devu: 2012-03-05 10:03:56 how to take input?
	well i am lagging: 2012-03-02 04:53:07 hey my mistake not 10^7 but sqrt(10^7) accepted :) Last edit: 2012-03-02 05:18:32
	Ikhaduri: 2012-02-29 17:36:27 :@ RAJDEEP it will work, but if you have th O(n) sieve, that stores first(minimal) factors of each number, from 1 to 10^7
	RAJDEEP GUPTA: 2012-02-28 18:14:54 will sieve of eratothenes work?? I implemented it but got tle!! but still i want to know as it might be my mistake. EDIT: Thanks. AC. :) Last edit: 2012-03-02 04:26:55
	Pranay: 2012-02-28 06:11:00 Even Pollard-Rho gives TLE in java Last edit: 2012-03-01 17:36:28

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