Exercise 11-8 Greatest Common Divisor

#include <stdio.h>

int gcd(int a, int b);
int gcdIter(int a, int b);

int main(void) {
  int a,b;

  printf("\nGreatest common divisor\n");
  printf("\nEnter the first number: \n");
  scanf("%i",&a);
  printf("\nEnter the second number: \n");
  scanf("%i",&b);
  
  printf("\nGreatest common divisor by recursion: %i\n",gcd(a,b));
  printf("\nGreatest common divisor by iteration: %i\n",gcdIter(a,b));

  return 0;
}


int gcd(int a, int b) {
  int r; 

  if ((r = a % b) == 0) {
    return b;
  } else {
    return gcd(b,r);
  }
}


int gcdIter(int a, int b) {
  int minVal, maxVal, i; 

  if (a > b) {
    maxVal = a;
    minVal = b;
  } else {
    maxVal = b;
    minVal = a;
  } 

  i = minVal;
  while (i >= 1) {
    if (((maxVal % i) == 0) && ((minVal % i) == 0)) {
      return i;
    } else {
      i--;
    }
  }
  return i;
}

	#include <stdio.h> int gcd(int a, int b); int gcdIter(int a, int b); int main(void) { int a,b; printf("\nGreatest common divisor\n"); printf("\nEnter the first number: \n"); scanf("%i",&a); printf("\nEnter the second number: \n"); scanf("%i",&b);
	The usual initial matter: include stdio.h, declare function prototypes, start the main() function, declare variables, print an introductory text, and receive data input from the user.

 

	printf("\nGreatest common divisor by recursion: %i\n",gcd(a,b));
	Here we start the recursion. gcd() is called with the entered data as arguments. It eventually returns the greatest common divisor, which is then printed out.

 

	printf("\nGreatest common divisor by iteration: %i\n",gcdIter(a,b));
	Does the same as the line above, except the iterative version is called.

 

int gcd(int a, int b) { int r; if ((r = a % b) == 0) { return b; } else { return gcd(b,r); } }

This is the recursive function. Without going into too much detail about _why_ it works, the strategy is as follows: divide one of the numbers by the other and find the remainder. If the remainder is zero, the divisor is the greatest common divisor. If the remainder is different from zero, we divide the divisor by the remainder (i.e., execute gcd() on the divisor and the remainder). If the remainder is zero, the new divisor is the greatest common divisor. If not, we continue to divide the new divisor by the new remainder, until we reach a remainder of zero.

 

	int gcdIter(int a, int b) { int minVal, maxVal, i; if (a > b) { maxVal = a; minVal = b; } else { maxVal = b; minVal = a; } i = minVal; while (i >= 1) { if (((maxVal % i) == 0) && ((minVal % i) == 0)) { return i; } else { i--; } } return i; }
	The iterative version of the function implemented here is much less elegant, but it works. We find the minimum and maximum value of the two supplied values. Then we start at the smallest of the two values and test if i divides both values without remainder. If it does, we return i; if not, we decrease i and try again.