Euclidean Algorithm to compute GCD of 2 numbers

Euclidean Algorithm

Here we assume that a is greater than b

(a>b)

gcd_euclid(int a, int b)
{
         if( b is 0) return a
     
        else
            {
              set value of a as b
              set value of b as a modulo b
            }
}

When 2 prime no's are taken,GCD is usually 1 and it can be seen from below example.... 

1. gcd_euclid(19,5)
2. gcd_euclid(5,19%5)
3. gcd_euclid(5,4)
4. gcd_euclid(4,5%4)
5. gcd_euclid(4,1)
6. gcd_euclid(1,4%1)
7. gcd_euclid(1,0)

return 1; //as b is 0.

GCD when 2 non prime no's are taken.....

1. gcd_euclid(30,5)
2. gcd_euclid(5,30%5)
3. gcd_euclid(5,0)

return 5; // as b is 0

Programmatic Implementation:

int euclid(int a, int b)
{
   while (b!=0)
   {
       int temp = b;
       int b = a%b;
       int a = temp;
   }

return a;
}

Thank You :)