Saturday, November 14, 2009

Greatest Common Divisor and Least Common Multiple functions in C

Below are two functions (with a sample application) that calculate the Greatest Common Divisor and Least Common Multiple of two numbers; a,b

#include <stdio.h>

int gcd(int x, int y);
int lcm(int x, int y);

int main()
{
    int x = 156;
    int y = 156;

    int g = gcd(x,y);
    int l = lcm(x,y);

    printf("GCD (%d, %d) : %d\n", x,y,g);
    printf("LCM (%d, %d) : %d\n", x,y,l);
}

int gcd(int x, int y) {
    /*;
        a = qb + r,  0 <= r < b

        a => dividend, q => quotient, b => divisor, r => remainder
    */
    if (x == y) {
        return x /*or y*/;
    }

    int dividend = x, divisor = y, remainder = 0, quotient = 0;

    do {
        remainder = dividend % divisor;
        quotient = dividend / divisor;

        if(remainder) {
            dividend = divisor;
            divisor = remainder;
        }
    }
    while(remainder);

    return divisor;
}

int lcm(int x, int y) {
    /*
        lcm(x,y) = (x * y) / gcd(x,y)
    */
    return x == y ? x /*or y*/ : (x * y) / gcd(x,y);
}