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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#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);
}

Comments (3)

Loading... Logging you in...
  • Logged in as
First off I really like your blog! so much information.
I understand how the conditions work now on lines 34 and 39. Thank you!
1 reply · active 791 weeks ago
Michael,
Thanks for following my blog.
If you have any more questions about that code, please do not hesitate to ask me; will be glad to help ;-)
Fonda Shibley's avatar

Fonda Shibley · 518 weeks ago

Thanks for sharing this step by step guide here. That's very helpful to learn least and divisor function. In dreasgrech blog there are many impressive things which we can learn easily. essay writing companies

Post a new comment

Comments by