Greatest Common Divisor - GCD

Recursion Algorithm

Share

What is GCD or Greatest Common Divisor

In mathematics GCD or Greatest Common Divisor of two or more integers is the largest positive integer that divides both the number without leaving any remainder.
Example:
GCD of 20 and 8 is 4

The pseudo code of GCD [recursive]


GCD(x, y)
Begin
      if y = 0 then
          return x;
      else
          Call: GCD(y, x%y);
      endif
End

Find the GCD of 48 and 14 recursively

To find the GCD we have to divide 48 by 14


14 ) 48 ( 3
     42
     -----
      6

Remainder is not yet zero, so we will now divide 14 by 6

14 ) 48 ( 3
     42
     -----
      6 ) 14 ( 2
          12
          -----
           2

Remainder is not yet zero, so we will now divide 6 by 2

14 ) 48 ( 3
     42
     -----
      6 ) 14 ( 2
          12
          -----
           2 ) 6 ( 3
               6
               ----
               0

Remainder is 0 so, we stop here

Therefore, the required GCD is 2

GCD code in C


#include <stdio.h>
int gcd(int x, int y);

int main(){
	int a, b, g;

	printf("Enter a and b:\n");
	scanf("%d%d", &a, &b);

	//gcd
	g = gcd(a, b);

	//in case g is negative, then convert it into positive
	if(g < 0){
		g *= -1;
	}

	//output
	printf("GCD(%d, %d) = %d\n", a, b, g);
	return 0;
}

int gcd(int x, int y){
	if(y == 0) return x;
	else gcd(y, x%y);
}

Recently Added