Description

Lab09. GCD and LCM
Given any positive integer N, one can express this integer as a product of its prime factors. For example, if N = 100 then
N = 22× 52. (9.1)
Given two positive integers, N1 and N2, once both are expressed in the product of prime factors form, their Greatest Common Divisor (GCD) and Least Common Multiple (LCM) can also be found easily. For example, if N1 = 100 and N2 = 225, then
N1 = 22× 52 N2 = 32× 52
GCD(N1,N2) = 52 = 25 (9.2)
(9.3)
(9.4)
LCM(N1,N2) = 22× 32× 52 = 900 (9.5)
In this assignment, you will write a C program with the following functions.
1. void factorize(int N,int factors[S],int power[S]);
This function factorizes the input N into its prime factors (factors array) and their powers (power array). Using N1 = 100 as an example, after calling the factorize function, the two arrays’ contents are:
factors[] = {2,5,1}; (9.6)
power[] = {2,2,1}; (9.7)
Note that in the factors array the prime factors are ordered in ascending order and is terminated by 1. And, S is a predefined macro.
#define S 20
2. void GCD(int Afactors[S],int Apower[S],int Bfactors[S],int Bpower[S], int Cfactors[S],int Cpower[S]);
This function takes two factors arrays and two power arrays to produce two output arrays: one for GCD factors and the other for GCD power. Following the convention, the Cfactors should have the prime factors ordered in ascending order.
3. void LCM(int Afactors[S],int Apower[S],int Bfactors[S],int Bpower[S], int Cfactors[S],int Cpower[S]);
This function takes two factors arrays and two power arrays to produce two output arrays: one for LCM factors and the other for LCM power. Again, the Cfactors array is in ascending order.
4. void write(int factors[S],int power[S]);
This function prints out the factors and power arrays in product of prime factor form and the integer calculated using this product from. For example, with the arrays produced by the factorize function above, it prints out
2ˆ2 * 5ˆ2 = 100 (9.8)
Your C program reads in two integers at the beginning and then factorizes these two integers. Using the factors and power arrays, the GCD and LCM are then found and printed out. Example inputs and outputs of your program are shown below.

$ ./a.out input A: 100 input B: 225
A = 2^2 * 5^2 = 100
B = 3^2 * 5^2 = 225GCD(A,B) = 5^2 = 25
LCM(A,B) = 2^2 * 3^2 * 5^2 = 900
$ ./a.out input A: 24 input B: 35
A = 2^3 * 3 = 24 B = 5 * 7 = 35
GCD(A,B) = 1 = 1
LCM(A,B) = 2^3 * 3 * 5 * 7 = 840

Notes.
1. Create a directory lab09 and use it as the working directory.
2. Name your program source file as lab09.c.
3. The first few lines of your program should be comments as the following.
*/
4. After you finish verifying your program, you can submit your source code by
$ ∼ee231002/bin/submit lab09 lab09.c
If you see a ”submitted successfully” message, then you are done. In case you want to check which file and at what time you submitted your labs, you can type in the following command:
$ ∼ee231002/bin/subrec
It will show the last few submission records.
5. You should try to write the program as efficient as possible. The format of your program should be compact and easy to understand. These are part of the grading criteria.