Euclids GCD Algorithm

By | August 31, 2015

Greatest Common Divisor- Euclid’s Algorithm

Problem:

Given two numbers M and N, find their GCD.

Example:

M=36  N=48
Answer: 12

Solution:

The GCD or Greatest common divisor of two numbers can be calculated using Euclid’s Algorithm for GCD which is given below:

while( n is not divisible by m)
{
     rem = n mod m;
     n=m;
     m=r;
}

The value of ‘r’ is the GCD required

Lets take an example, let m=36 and n=48,
48 is not divisible by 36, thus,

Iteration 1:
rem=12 (48%36)
n=36 ( Previous m)
m=12 (rem is 12)

Now, 36(n) is divisible by 12(m), thus, the loop will not work!
Coming onto the next equation after the loop, the value of ‘r (12)’ is the required answer.

Here is the working Code:

Iterative:

#include <stdio.h>
int main()
{
     int m,n,r;
     m=36; n=48;
     while(n%m)
 	{
 		r=n%m;
 		n=m;
 		m=r;
 	}
 	printf("%d",r);
 	return 0;
}

Recursive:

#include <stdio.h>

int gcd(int n,int m)
{ 
     if(n==0)
          return(m);
     else 
          return(gcd(m%n,n));
 }
 
int main()
{
     int m,n,r;
     m=36; n=48;
     r=gcd(n,m);
     printf("%d",r); 
     return 0;
}

Output:

12