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

hide comments
Man Mohan Mishra: 2013-12-19 16:44:48

nice problem...
tried something new in it.. :)

Anand Kr Shaw : 2013-10-18 16:04:05

i printed all the testcases and checked upto 10^7,....did not find any mistake...getting wa ...help ???

Rana Saha: 2013-09-21 18:31:26

AC at first Try!
Normal Sieve + little bit of trick !! :-P

NodaR M JarraR: 2013-09-02 04:55:42

finally done after 20 submissions it is so exciting problem :) i am so glad :D

Akhilesh Anandh: 2013-08-26 09:49:45

@Phylippe Mederios: Can u please tell me why I'm getting WA? Submission id 9915663. Is it because my output format is wrong?

Last edit: 2013-08-26 10:34:36
Santiago Palacio: 2013-05-30 17:49:18

I guess the key is to STRONGLY optimize output here.

Ouditchya Sinha: 2013-05-02 13:44:00

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?

[Lakshman]: 2013-02-20 09:48:03

Finally AC after unlimited TLE..no Pollard Roh only optimized sieve with naive factor function.....

Last edit: 2013-04-13 17:17:53
lunaram: 2013-02-20 05:10:20

15th submission
finaly AC.......

saket diwakar: 2013-01-26 15:10:24

yeah.......finally AC with 8.33s...:)

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

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