Uva 583 Prime Factors

Problem: 583.Prime Factors

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.,

$\begin{displaymath}g = f_1 \times f_2 \times \dots \times f_n \end{displaymath}$

is unique if we assert that f_i > 1 for all i and $f_i \le 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³¹ - 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³¹ < g <2³¹

, but different of -1 and 1. 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 $g>0, g = f_1 \times f_2 \times \dots \times f_n$ , where each f_i is a prime number greater than unity (with $f_i \le f_j$ for i<j), the format of the output line should be

$\begin{displaymath}g \mbox{\tt\ = } f_1 \mbox{\tt\ x } f_2 \mbox{\tt\ x } \dots \mbox{\tt\ x } f_n \end{displaymath}$

When g < 0, if $\mid g \mid = f_1 \times f_2 \times \dots \times f_n$ , the format of the output line should be

$\begin{displaymath}g \mbox{\tt\ = -1 x } f_1 \mbox{\tt\ x } f_2 \mbox{\tt\ x } \dots \mbox{\tt\ x } f_n \end{displaymath}$

Sample Input

Sample Output

-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

Description of the Solution:

Algorithm:
1. Generate prime number in a array.
2. Divide the given number by the array element until arr[ele]<=sqrt(input). print arr[ele].
3. Print output carefully.
How we generate prime number:
Let: p[]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}; ie p[ele]=1 means ele is a prime.
Take i=2 which is prime, Now p[2]=0,p[4]=0,p[6]=0,p[8]=0,p[10]=0;p[12]=0;p[14]=0;
So now p[]={1,1,1,1,0,0,1,0,1,0,1,0,1,0,1}
Take i=3 which is prime, Now p[6]=0,p[9]=0;p[12]=0;p[15]=0;
So now p[]={1,1,1,1,0,1,0,1,0,0,0,1,0,1,0,0}
For i=4 , i<=sqrt(16) false so end
P[0]=1 ;p[1]=1,p[2]=1;p[3]=1;p[5]=1,p[7]=1;p[11]=1;p[13]=1;
Move a[0]=0,a[1]=1;a[2]=2;a[3]=3;a[4]=5;a[5]=7;a[6]=11;a[7]=13

Code In C/C++:

Rizoan Toufiq