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
# Python code to demonstrate naive# method to compute gcd ( recursion )def hcfnaive(a, b): if(b == 0): return abs(a) else: return hcfnaive(b, a % b)a = 60b = 48# prints 12print("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
# Python code to demonstrate naive# method to compute gcd ( Loops )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 gcda = 60b = 48# prints 12print ("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
# Python code to demonstrate naive# method to compute gcd ( Euclidean algo )def computeGCD(x, y): while(y): x, y = y, x % y return abs(x)a = 60b = 48# prints 12print ("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.
