C Programming only.

Please fill in the missing code in the FIVE designated areas in source file Problem22.c that says "Student provides missing code......" below.

I've put some brief info on the GCD algorithms that need to be implement. PLEASE DO ALL 4 of the GCD Algorithms asked in the Problem.

PLEASE also provide screenshot of the compiled output once complete. I have provided a sample one which should give an idea on how it should look.

Euclids algorithm is based on applying repeatedly the equality

gcd(m, n) = gcd(n, m mod n),

where m mod n is the remainder of the division of m by n, until m mod n is equal to 0. Since gcd(m, 0) = m (why?), the last value of m is also the greatest common divisor of the initial m and n.

For example, gcd(60, 24) can be computed as follows: gcd(60, 24) = gcd(24, 12) = gcd(12, 0) = 12.

Euclids algorithm for computing gcd(m, n)

Step 1 If n = 0, return the value of m as the answer and stop; otherwise, proceed to Step 2.

Step 2 Divide m by n and assign the value of the remainder to r.

Step3 Assign the value of n to m and the value of r to n. Go to Step1.

Consecutive integer checking algorithm for computing gcd(m, n)

Step 1 Assign the value of min{m, n} to t

Step 2 Divide m by t. If the remainder of this division is 0, go to Step 3; otherwise, go to Step 4.

Step 3 Divide n by t. If the remainder of this division is 0, return the value of t as the answer and stop; otherwise, proceed to Step 4.

Step 4 Decrease the value of t by 1. Go to Step 2.

Middle-school procedure for computing gcd(m, n)

Step 1 Find the prime factors of m

Step 2 Find the prime factors of n.

Step 3 Identify all the common factors in the two prime expansions found in Step 1 and Step 2. (If p is a common factor occurring pm and pn times in m and n, respectively, it should be repeated min{pm, pn} times.)

Step 4 Compute the product of all the common factors and return it as the greatest common divisor of the numbers given.

Thus, for the numbers 60 and 24, we get

60 = 2 . 2 . 3 . 5

24 = 2 . 2 . 2 . 3 gcd(60, 24) = 2 . 2 . 3 = 12.

//--------------------------------------------------

// Problem #22

// Problem22.c

//--------------------------------------------------

#include

#include

#include

#include

#include

#define MAXFACTORS 1024

// Commented-out in lieu of using definition of the bool data type

// typedef enum { false = 0,true = 1 } boolean;

typedef struct

{

int size;

int factor[MAXFACTORS+1];

int exponent[MAXFACTORS+1];

} FACTORIZATION;

//--------------------------------------------------

int main()

//--------------------------------------------------

{

int GCD1(int m,int n);

int GCD2(int m,int n);

int GCD3(int m,int n);

int GCD4(int m,int n);

int m,n;

printf("m? ");

while ( scanf("%d",&m) != EOF )

{

printf("n? "); scanf("%d",&n);

printf("GCD1(m,n) = %d ",GCD1(m,n));

printf("GCD2(m,n) = %d ",GCD2(m,n));

printf("GCD3(m,n) = %d ",GCD3(m,n));

printf("GCD4(m,n) = %d ",GCD4(m,n));

printf("m? ");

}

system("PAUSE");

return( 0 );

}

//--------------------------------------------------

int GCD1(int m,int n)

//--------------------------------------------------

{

Student provides missing code to implement the iterative formulation of

Euclids algorithm for computing the greatest common divisor.

}

//--------------------------------------------------

int GCD2(int m,int n)

//--------------------------------------------------

{

Student provides missing code to implement the Consecutive Integer Checking

algorithm for computing the greatest common divisor. You should ensure

the pre-condition ((m 0) and (n 0)) is satisfied.

}

//--------------------------------------------------

int GCD3(int m,int n)

//--------------------------------------------------

{

void FindFactorization(int x,FACTORIZATION *factorization);

void DisplayFactorization(int x,FACTORIZATION factorization);

FACTORIZATION mFactorization;

FACTORIZATION nFactorization;

int r,mi,ni;

// Step 1.

FindFactorization(m,&mFactorization);

DisplayFactorization(m,mFactorization);

// Step 2.

FindFactorization(n,&nFactorization);

DisplayFactorization(n,nFactorization);

// Steps 3 and 4.

Student provides missing code to implement Steps 3 and 4 of the Middle-School

Procedure algorithm for computing the greatest common divisor.

}

//--------------------------------------------------

void FindFactorization(int x,FACTORIZATION *factorization)

//--------------------------------------------------

{

int NextPrime(int x);

Student provides missing code to find the prime factors of x. For example, if

x = 14850 = 1*2*3³*5²*11, then *factorization would look like

factorization->size = 5

factorization->factor[1:5] = 1 2 3 5 11

factorization->exponent[1:5] = 1 1 3 2 1

}

//--------------------------------------------------

void DisplayFactorization(int x,FACTORIZATION factorization)

//--------------------------------------------------

{

int i;

printf("%d = ",x);

for (i = 1; i

{

printf("%d",factorization.factor[i]);

if ( factorization.exponent[i] > 1 )

printf("^%d",factorization.exponent[i]);

if ( i

printf("*");

else

printf(" ");

}

}

//--------------------------------------------------

int NextPrime(int x)

//--------------------------------------------------

{

bool IsPrime(int x);

do

x++;

while ( !IsPrime(x) );

return( x );

}

//--------------------------------------------------

bool IsPrime(int x)

//--------------------------------------------------

{

int i;

bool r = true;

for (i = 2; (i

r = r && ((x % i) != 0);

return( r );

}

//--------------------------------------------------

int GCD4(int m,int n)

//--------------------------------------------------

{

Student provides missing code to implement the recursive formulation of

Euclids algorithm for computing the greatest common divisor.

}

Problem Write a single C program that implements 4 of the 4 GCD algorithms GCDI0 (the iterative formulation of Euclid's algorithm) GCD20 (the "Consecutive Integer Checking" algorithm) GCD30 (the "Middle-School Procedure" algorithm) GCD40 (the recursive formulation of Euclid's algorithm) Sample Program Dialo m? 11 n? 7 GCD1 (mn)-1 GCD2 (m.n) 1 7-1*7 GCD3 (man) 1 n? 6 GCD1 (m, ) -3 GCD2 (msn) = 3 913 2 61*2 3 m? 24 n? 60 GCD1 (mn) -12 GCD2 (mn)-1.2 24 - 1 2 33 60-1*2 2 3 5 GCD4 (mon)-12 m? 31415 n? 14142 GCD1 (mun) 1 GCD2 (m,n) -1 31415 15 61 103 14142 -12*3*2357 GCD3 (mn)-1 GCD4 (Men) = 1