Thursday, June 9, 2011

GCD & LCM

GCD: Greatest Common Divisor:


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


int LCM(int a, int b)
{
   return b*a/GCD(a,b);
}
Euclid's algorithm can be used to solve linear Diophantine equations. These equations have integer coefficients and are of the form:
ax + by = c

No comments :