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 : 12Way 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 : 12Way 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) : 5Code #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