# Gcd (C)

### From LiteratePrograms

**Other implementations**: bc |**C**

This implements the Euclidean Algorithm in C in two different ways to find the Greatest Common Divisor of two integers 'a' and 'b'.

The first is a recursive definition.

#include <stdio.h>#include <stdlib.h>intgcd(unsignedinta,unsignedintb){if(a%b<1){return(b);}gcd(b,a%b);}intmain(intargc,char*argv[]){printf("%d\n",gcd(atoi(argv[1]),atoi(argv[2])));return(0);}

The second uses a while loop.

#include <stdio.h>#include <stdlib.h>intmain(intargc,char*argv[]){intnumerator, denominator, remainder; numerator=atoi(argv[1]); denominator=atoi(argv[2]);while(denominator != 0){remainder = numerator % denominator; numerator = denominator; denominator = remainder;}printf("%d\n",numerator);return(0);}

Here is yet another implementation that shows each step when computing the Greatest Common Divisor of two integers. This is useful for teaching purposes.

From the Division "Algorithm", we know that:
for any integers '**a'**, and '**b'** > 0, there exist integers '**q'** and '**r'** such that
'**q'** and '**r'** are unique (they are determined by '**a'** and '**b'**)
and

The variable '**a,b,q,r'** names used here stand for:
'**a'** usually stands for the numerator of a fraction
'**b'** usually stands for the denominator of a fraction
'**q'** for **q**uotient
'**r'** for **r**emainder

Computing the **gcd** of two integers using the Euclidean Algorithm makes repeated use of this fact.

#include <stdio.h>#include <stdlib.h>intmain(intargc,char*argv[]){intnumerator, denominator, quotient, remainder; numerator=atoi(argv[1]); denominator=atoi(argv[2]); printf("a=b*q + r\n");while(denominator != 0){quotient = numerator / denominator; remainder = numerator % denominator; printf("%d=%d*%d + %d\n",numerator,denominator,quotient,remainder); numerator = denominator; denominator = remainder;}printf("0=%d*%d + %d -- STOP\n",denominator,quotient,remainder); printf("GCD = %d\n",numerator);return(0);}

Download code |