http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=524

Prime Factors

Webster defines prime as:

prime (prim) 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 prime 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.,

is unique if we assert that f_i > 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 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 =  f1 x f2 x ... x fn, where each f_i is a prime number greater than unity (with fi <fj for i<j), the format of the output line should be

When g < 0, if | g | =  f1 x f2 x ... x fn, the format of the output line should be

Sample Input 

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

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

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

#include <stdio.h>
#include <math.h>
 
void print_factors(long n);
 
int main(int argc, char **argv)
{
        long n;
        while (1)
        {
                scanf("%ld", &n);
                if (n==0)
                {
                        break;
                }
                printf("%ld = ", n);
                if (n<0)
                {
                        printf("-1 x ");
                        n = -n;
                }
                print_factors(n);
                printf("\n");
        }
        return 0;
}
 
void print_factors(long n)
{
        int first = 1;
        while (n%2==0)
        {
                if (first)
                {
                        printf("2");
                        first = 0;
                }
                else
                {
                        printf(" x 2");
                }
                n /= 2;
        }
        long i = 3;
        long sqn = (sqrt(n))+1;
        while (i <= sqn)
        {
                if ((n%i)==0)
                {
                        if (first)
                        {
                                printf("%ld", i);
                                first = 0;
                        }
                        else
                        {
                                printf(" x %ld", i);
                        }
                        n /= i;
                }
                else
                {
                        i += 2;                 
                }
        }
        if (n>1)
        {
                if(first)
                {
                        printf("%ld", n);
                }
                else
                {
                        printf(" x %ld", n);
                }
        }
}