*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* = *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

This page maintained by
Ed Karrels.

Last updated December 10, 1999