I am going to cover a very simple algorithm this time. It is the GCD(Greatest Common Divisor) algorithm. The GCD of two numbers a and b is the greatest number c such that a%c==0 and b%c==0.

The naive algorithm to find the GCD of two numbers is something like this:

int GCD(int a, int b)
{
int i=MIN(a,b);
while(i>=1)
{
if(a%i==0 && b%i==0)
break;
i--;
}
return i;
}

Here we start from MIN(a,b) and find the highest number that is a factor of both a and b; and return it. Simple algorithm but not too efficient.

A better algorithm for finding the GCD of two numbers is the Euclidean algorithm. The implementation is as follows:

int GCD(int a,int b)
{
if(a%b==0)
return b;
return GCD(b,a%b);
}

This is a recursive algorithm. The function takes two numbers a and b. If b is a factor of a, then obviously the GCD of a and b is b. But if it is not, then the GCD of a and b is the GCD of b and a%b.

In other words, we take two numbers a and b and divide them. At each step, the remainder of the previous division becomes the divisor and the divisor of the previous division becomes the divident. We repeat this until the remainder becomes zero. The divisor when the remainder becomes zero is the GCD of a and b.

I’m sure most of you have done the Euclidean algorithm when you were in school. Maybe the image on this page will help refresh your memory:

http://f-of-x.blogspot.in/2010/04/euclids-algorithm-for-finding-gcf.html

### Like this:

Like Loading...

*Related*