SPOJ Problem Set (classical)

10818. Medium Factorization

Problem code: FACTCG2

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

Sample Output

1 x 2

1 x 2 x 2

1 x 2 x 2 x 2

Added by:	Phyllipe Medeiros
Date:	2012-02-26
Time limit:	6s
Source limit:	50000B
Memory limit:	256MB
Cluster:	Pyramid (Intel Pentium III 733 MHz)
Languages:	All

hide comments

2013-05-30 19:49:18 Santiago Palacio
I guess the key is to STRONGLY optimize output here.

2013-05-02 15:44:00 Ouditchya Sinha
Man, this question is something else... I used Sieve of Atkins for generating primes upto 10^7 & then used optimised factorisation to get AC in 12.48s. How is 2.24s possible? Pollard Rho or any other technique?

2013-02-20 10:48:03 Lakshman
Finally AC after unlimited TLE..no Pollard Roh only optimized sieve with naive factor function.....

Last edit: 2013-04-13 19:17:53

2013-02-20 06:10:20 lunaram
15th submission
finaly AC.......

2013-02-02 23:50:31 Sparik

Last edit: 2013-04-13 00:06:30

2013-01-26 16:10:24 saket diwakar
yeah.......finally AC with 8.33s...:)

Last edit: 2013-01-26 16:11:32

2013-01-23 04:12:35 Diogo Soares [UFAM]
Is there any ideal strategy to pass this question in less than 10 seconds. O(n) takes > 10 s with optmization

2013-01-20 03:20:41 DivineAtheist
Finally got AC...Now i wonder how people got AC in just 2.03 seconds...Even polard rho is giving TLE here...

Last edit: 2013-01-20 03:21:53

2013-01-19 21:13:01 Noob..!!
clears the concept of prime factorization..!!

2012-11-09 12:04:31 :-P
please correct the problem in the description it says “ x” but in the example it's “ x ”
I'm getting wa not tle

Last edit: 2012-11-09 12:11:03