Is there any gcd function in python?

View Discussion

Improve Article

Save Article

View Discussion

Improve Article

Save Article

The Highest Common Factor (HCF), also called gcd, can be computed in python using a single function offered by math module and hence can make tasks easier in many situations.

Naive Methods to compute gcd

Way 1: Using Recursion

Python3

def hcfnaive(a, b):

    if(b == 0):

        return abs(a)

    else:

        return hcfnaive(b, a % b)

a = 60

b = 48

print("The gcd of 60 and 48 is : ", end="")

print(hcfnaive(60, 48))

Output

The gcd of 60 and 48 is : 12

Way 2: Using Loops 

Python3

def computeGCD(x, y):

    if x > y:

        small = y

    else:

        small = x

    for i in range(1, small + 1):

        if((x % i == 0) and (y % i == 0)):

            gcd = i

    return gcd

a = 60

b = 48

print ("The gcd of 60 and 48 is : ", end="")

print (computeGCD(60,48))

Output

The gcd of 60 and 48 is : 12

Way 3: Using Euclidean Algorithm 

Python3

def computeGCD(x, y):

   while(y):

       x, y = y, x % y

    return abs(x)

a = 60

b = 48

print ("The gcd of 60 and 48 is : ",end="")

print (computeGCD(60, 48))

Output:

The gcd of 60 and 48 is : 12

• Both numbers are 0, gcd is 0
• If only either number is Not a number, Type Error is raised.