Description
EE231002 Introduction to Programming
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 × 5
2
. (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 × 5
2
(9.2)
N2 = 32 × 5
2
(9.3)
GCD(N1, N2) = 52 = 25 (9.4)
LCM(N1, N2) = 22 × 3
2 × 5
2 = 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
1
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 = 225
GCD(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.
/* EE231002 Lab09. GCD and LCM
ID, Name
Date:
*/
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.
2
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.
3
