Sunday, July 27, 2008

GCD LCM

GCD for 60 and 40 is 20: 

60 = 40 * 1 + 20
40 = 20 * 2 + 0

LCM for 60 and 40 is 120:
60*40 / 20

int gcd(a, b):
    if b==0:
        return a
    return gcd(b, a%b)


int gcd(a, b):
    while (b != 0):
        temp = a%b
        a = b
        b = t
    return a


int lcm(a, b):
    return (a*b)/gcd(a, b)


[Hat tip to D at topcoder]

No comments:

Post a Comment