ACM Regional Programming Contest 1998
Problem No.  4  - Prime Factors
Executable Program: PROG4.EXE, PROG4.CLASS
Source Program: PROG4.CPP, PROG4.C, PROG4.JAVA, PROG4.PAS
Input file: IN.TXT   Output file: OUT.TXT
 
 

    Problem Description:

    Webster defines prime as:
prime (prim) n. 1 : first in time :
original 2 a : having no factor except itself and one < 3 is a ~ number i > 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 >
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 x f2 x . . . x fn

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

Input

The input will consist of a sequence of numbers. Each line of input will contain one number g
in the range  -250 <= g <= 250. 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 x f2 x . . . x 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 > x < f2 > x ... x < fn >

If 0 > g = f1 x f2 x . . . x fn, the format of the output line should be

       < g > =  -1  x  < f1 > x < f2 > x ... x < fn >
 

 Example

The following is sample input for this problem.

-190
-191
-192
-193
-194
195
196
197
198
12
199
200
0

The following is the corresponding output for the input above.

**********************
* Team ##, Problem 4 *
**********************

-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