Greatest common divisor and LCM of two number by using Python

By Vishal Kumar

Greatest common divisor naive algorithm and using Euclid,s lemma for faster algorithm by recursion of very high number. And also exploiting the relation between GCD and LCM in Python

Greatest common divisor of two number is nothing but highest common factor or divisor of two number. One can use elementary school technique to write the naive algorithm but for large number it will run very slow.

Naive Algorithm for GCD:

Below is the Python code:

def gcd(a,b):
    best=0
    if a>b:
        if a%b==0:
            return b
        else:
            for i in range(1,b//2+1):
                if b%i==0 and a%i==0:
                    best=i
            return best
    else:
        if b%a==0:
            return a
        else:
            for i in range(1,a//2+1):
                if b%i==0 and a%i==0:
                    best=i
            return best

To make the efficient algorithm which can work on very large number say upto range of 10**18. we can use euclid,s lemma. According to this gcd(a,b) is equal to gcd of remainder,when a is divided by b and b. i.e(gcd(a%b,b)).This will remain equal untill and unless remainder of that two number become zero. And the that number due to which  remainder become zero is greatest common divisor. We can implement this logic by recursion.

Faster Algorithm for GCD:

def gcd2(a,b):
    if a>b:
        if a%b==0:
            return b
        else:
            a=a%b
            return gcd2(a,b)
    else:
        if b%a==0:
            return a
        else:
            b=b%a
            return gcd2(a,b)

Two find out the LCM of two number we can explot the relation between GCD, LCM and product of two number. That is product of two number is equal to product of GCD and LCM.

Faster Algoritrhm of LCM:

def gcd2(a,b):
    if a>b:
        if a%b==0:
            return b
        else:
            a=a%b
            return gcd2(a,b)
    else:
        if b%a==0:
            return a
        else:
            b=b%a
            return gcd2(a,b)
def lcm(a,b):
    return (a*b/gcd2(a,b))