Not an official ACM page
[Problem 7 | 1997 East-Central problem set | Ed's programming contest problem archive | my home page]

## ACM East Central Region 1997 Regional Programming Contest

### Problem 6 - Prime Factors

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 <3 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 decompositon of a positive number g into its prime factors, i.e.,

g = f1 × f2 × ... × fn

is unique if we assert that fi > 1 for all i and fi <= fj for i < j.

One interesting class of prime numbers are the so-called Mersenne primes which are of the form 2p - 1. Euler proved that 231 - 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 -231 < g < 231. 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 = f1 × f2 × ... × fn, where each fi is a prime number greater than unity (with fi <= fj for i < j), the format of the output line should be
<g> = < f1 > × < f2 > × ... × < fn >
If 0 > g = f1 × f2 × ... × fn, the format of the output line should be
<g> = -1 × < f1 > × < f2 > × ... × < fn >

```-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
```