GCD and LCM Solution

$30.00

Description

Given any positive integer N , N > 1, one can express this integer as a product of its prime factors. For example, if N = 100 then

N = 22 52:

(10.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

(10.2)

N2

= 32

52

(10.3)

GCD(N1; N2) = 52

= 25

(10.4)

LCM(N1; N2) = 22

32 52 = 900

(10.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 asso-ciated powers (power array). Using N1 = 100 as an example, after calling the factorize function, the two arrays’ contents are:

factors[] = f2; 5; 1g;

(10.6)

power[] = f2; 2; 1g;

(10.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 50

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

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

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

(10.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

LCM(A,B) = 2^3 * 3 * 5 * 7 = 840

Notes.

  1. Create a directory lab10 and use it as the working directory.

  1. Name your program source file as lab10.c.

  1. The first few lines of your program should be comments as the following.

/* EE231002 Lab10. GCD and LCM ID, Name

Date:

*/

  1. After you finish verifying your program, you can submit your source code by

$ ee231002/bin/submit lab10 lab10.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 lab10

It will show the submission records of lab10.

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