Is there a 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.

View Discussion

Improve Article

Save Article

View Discussion

Improve Article

Save Article

In Python, math module contains a number of mathematical operations, which can be performed with ease using the module. math.gcd() function compute the greatest common divisor of 2 numbers mentioned in its arguments.

Syntax: math.gcd(x, y)

Parameter:
x : Non-negative integer whose gcd has to be computed.
y : Non-negative integer whose gcd has to be computed.

Returns: An absolute/positive integer value after calculating the GCD of given parameters x and y.

Exceptions : When Both x and y are 0, function returns 0, If any number is a character, Type error is raised.

Code #1:

import math 

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

print (math.gcd(60, 48)) 

Output:

The gcd of 60 and 48 is : 12

 
Code #2:

import math 

print ("math.gcd(44, 12) : ", math.gcd(44, 12))

print ("math.gcd(69, 23) : ", math.gcd(65, 45))

Output:

math.gcd(44, 12) :  4
math.gcd(69, 23) :  5

Code #3: Explaining Exception.

import math 

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

print (math.gcd(0, 0)) 

print ("\nThe gcd of a and 13 is : ", end ="") 

print (math.gcd('a', 13)) 

Output:

The gcd of 0 and 0 is : 0

The gcd of a and 13 is : 
TypeError: 'str' object cannot be interpreted as an integer