# 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