Webster defines prime as:

**prime** () *n*. [**ME**, fr. **MF**, fem. of *prin* first, **L** *primus*; akin to **L** *prior*] **1** : first in time; **original 2 a** : having no factor except itself and one ❤ is a ~ number> **b** : having no common factor except one <12 and 25 are relatively ~> **3 a**: first in rank, authority or significance : **principal b** : having the highest quality or value <~ television time> [from *Webster’s New Collegiate Dictionary*]

The most relevant definition for this problem is 2a: An integer *g* > 1 is said to be *prime* if and only if its only positive divisors are itself and one (otherwise it is said to be *composite*). For example, the number 21 is composite; the number 23 is prime. Note that the decomposition of a positive number *g* into its prime factors, i.e.,

*g* = *f*_{1} × *f*_{2} × … × *f*_{n}

is unique if we assert that *f*_{i} > 1 for all *i* and *f*_{i} <= *f*_{j} for *i* < *j*.

One interesting class of prime numbers are the so-called *Mersenne* primes which are of the form 2^{p} – 1. Euler proved that 2^{31} – 1 is prime in 1772 — all without the aid of a computer.

**Input**

The input will consist of a sequence of numbers. Each line of input will contain one number *g* in the range -2^{31} < *g* < 2^{31}. The end of input will be indicated by an input line having a value of zero.

**Output**

For each line of input, your program should print a line of output consisting of the input number and its prime factors. For an input number 0 < *g* = *f*_{1} × *f*_{2} × … × *f*_{n}, where each *f*_{i} is a prime number greater than unity (with *f*_{i} <= *f*_{j} for *i* < *j*), the format of the output line should be

<*g*> = < *f*_{1} > × < *f*_{2} > × … × < *f*_{n} >

If 0 > *g* = *f*_{1} × *f*_{2} × … × *f*_{n}, the format of the output line should be

<*g*> = -1 × < *f*_{1} > × < *f*_{2} > × … × < *f*_{n} >

**Sample Input**

-190

-191

-192

-193

-194

195

196

197

198

199

200

0

**Output for the Sample Input**

-190 = -1 x 2 x 5 x 19

-191 = -1 x 191

-192 = -1 x 2 x 2 x 2 x 2 x 2 x 2 x 3

-193 = -1 x 193

-194 = -1 x 2 x 97

195 = 3 x 5 x 13

196 = 2 x 2 x 7 x 7

197 = 197

198 = 2 x 3 x 3 x 11

199 = 199

200 = 2 x 2 x 2 x 5 x 5

using System;

using System.Collections.Generic;

using System.Text;

using System.Collections;

namespace ConsoleApplication1

{

class Program

{

static void Main(string[] args)

{

int num = -192;

ArrayList primeFactors = new ArrayList();

primeFactors = PrimeFactors(Math.Abs(num));

Console.Write(num + " = ");

if (num < 0)

{

Console.Write("-1" + " X ");

}

for (int i = 0; i < primeFactors.Count; i++)

{

if (i != primeFactors.Count – 1)

{

Console.Write(primeFactors[i] + " X ");

}

else

{

Console.Write(primeFactors[i]);

}

}

Console.WriteLine();

}

public static ArrayList PrimeFactors(int num)

{

ArrayList primeFactors = new ArrayList();

for (int i = 2; i <= num; i++)

{

if (IsPrime(i) && num % i == 0)

{

primeFactors.Add(i);

num = num / i;

i = 1;

}

}

return primeFactors;

}

public static bool IsPrime(int num)

{

if (num <= 1)

{

return false;

}

else if (num == 2)

{

return true;

}

else

{

for (int i = 2; i < num; i++)

{

if (num % i == 0)

{

return false;

}

}

return true;

}

}

}

}

-192 = -1 X 2 X 2 X 2 X 2 X 2 X 2 X 3

Press any key to continue . . .