In this example, you will learn to find the GCD of two numbers using two different methods: function and loops and, Euclidean algorithm
To understand this example, you should have the knowledge of the following Python programming topics:
- Python Functions
- Python Recursion
- Python Function Arguments
The highest common factor [H.C.F] or greatest common divisor [G.C.D] of two numbers is the largest positive integer that perfectly divides the two given numbers. For example, the H.C.F of 12 and 14 is 2.
Source Code: Using Loops
# Python program to find H.C.F of two numbers
# define a function
def compute_hcf[x, y]:
# choose the smaller number
if x > y:
smaller = y
else:
smaller = x
for i in range[1, smaller+1]:
if[[x % i == 0] and [y % i == 0]]:
hcf = i
return hcf
num1 = 54
num2 = 24
print["The H.C.F. is", compute_hcf[num1, num2]]
Output
The H.C.F. is 6
Here, two integers stored in variables num1 and num2 are passed to the compute_hcf[] function. The function computes the H.C.F. these two numbers and returns it.
In the function, we first determine the smaller of the two numbers since the H.C.F can only be less than or equal to the smallest number. We then use a for loop to go from 1 to that
number.
In each iteration, we check if our number perfectly divides both the input numbers. If so, we store the number as H.C.F. At the completion of the loop, we end up with the largest number that perfectly divides both the numbers.
The above method is easy to understand and implement but not efficient. A much more efficient method to find the H.C.F. is the Euclidean algorithm.
Euclidean algorithm
This algorithm is based on the fact that H.C.F. of two numbers divides their difference as well.
In this algorithm, we divide the greater by smaller and take the remainder. Now, divide the smaller by this remainder. Repeat until the remainder is 0.
For example, if we want to find the H.C.F. of 54 and 24, we divide 54 by 24. The remainder is 6. Now, we divide 24 by 6 and the remainder is 0. Hence, 6 is the required H.C.F.
Source Code: Using the Euclidean Algorithm
# Function to find HCF the Using Euclidian algorithm
def compute_hcf[x, y]:
while[y]:
x, y = y, x % y
return x
hcf = compute_hcf[300, 400]
print["The HCF is", hcf]Here we loop until y becomes zero. The statement x, y = y, x % y
does swapping of values in Python. Click here to learn more about swapping variables in Python.
In each iteration, we place the value of y in x and the remainder [x % y] in y, simultaneously. When y becomes zero, we have H.C.F. in x.
Here, in this section we will discuss how to find HCF of two numbers in python. HCF means [Highest Common Factor] also known as GCD [Greatest Common Divisor].
x is called HCF of a & b two conditions :
- x can completely divide both a & b leaving remainder 0
- No, other number greater than x can completely divide both a & b
What's on the Page
- Method 1: Linear Quest to find HCF
- Method 2: Euclidean Algorithm: Repeated Subtraction
- Method 3: Recursive Euclidean Algorithm: Repeated Subtraction
- Method 4: Modulo Recursive Euclidean Algorithm: Repeated Subtraction
- Method 5: Handling Negative Numbers in HCF
Method 1 : Linear Quest
Algorithm
- Initialize HCF = 1
- Run a loop in the iteration of [i] between [1, min[num1, num2]]
- Note down the highest number that divides both num1 & num2
- If i satisfies [num1 % i == 0 and num2 % i == 0] then new value of HCF is i
- Print value of HCF
Method 1 : Python Code
Run
num1 = 36
num2 = 60
hcf = 1
for i in range[1, min[num1, num2]]:
if num1 % i == 0 and num2 % i == 0:
hcf = i
print["Hcf of", num1, "and", num2, "is", hcf]Output
Method 2 : Repeated Subtraction
Algorithm
- Run a while loop until num1 is not equals to num2
- If num1>num2 then num1 = num1 – num2
- Else num2 = num2 – num1
- After the loop ends both num1 & num2 stores HCF
Method 2 : Python Code
Run
num1 = 36
num2 = 60
a = num1
b = num2
while num1 != num2:
if num1 > num2:
num1 -= num2
else:
num2 -= num1
print["Hcf of", a, "and", b, "is", num1]Output
Method 3 : Repeated Subtraction using Recursion
Algorithm
- Checked whether any of the input is 0 then return sum of both numbers
- If both input are equal return any of the two numbers
- If num1 is greater than the num2 then Recursively call findHCF[num1 – num2, num2]
- Else Recursively call findHCF[num1, num2-num1]
Method 3 : Python Code
Run
# Recursive function to return HCF of two number
def findHCF[num1, num2]:
# Everything divides 0
if num1 == 0 or num2 == 0:
return num1 + num2
# base case
if num1 == num2:
return num1
# num1>num2
if num1 > num2:
return findHCF[num1 - num2, num2]
else:
return findHCF[num1, num2 - num1]
num1 = 36
num2 = 60
print["Hcf of", num1, "and", num2, "is", findHCF[num1, num2]]Output
Method 4 : Repeated Subtraction with Modulo Operator using Recursion
Algorithm
- If b is equals to 0 return a
- Else recursively call the function for value b, a%b and return
Method 4 : Python Code
Run
# This method improves complexity of repeated subtraction
# By efficient use of modulo operator in euclidean algorithm
def getHCF[a, b]:
return b == 0 and a or getHCF[b, a % b]
num1 = 36
num2 = 60
print["Hcf of", num1, "and", num2, "is", getHCF[num1, num2]]‘
Output
Method 5 : Handling Negative Numbers in HCF
Algorithm
If any of the number is negative then convert it to positive by multiplying it with -1 as according to the proper definition HCF of two numbers can never be negative.
- If b is equals to 0 return a
- Else recursively call the function for value b, a%b and return
Method 5 : Python Code
Run
# This method improves complexity of repeated subtraction
# By efficient use of modulo operator in euclidean algorithm
def getHCF[a, b]:
return b == 0 and a or getHCF[b, a % b]
num1 = -36
num2 = 60
# if user enters negative number, we just changing it to positive
# By definition HCF is the highest positive number that divides both numbers
# -36 & 60 : HCF = 12 [as highest num that divides both]
# -36 & -60 : HCF = 12 [as highest num that divides both]
num1 >= 0 and num1 or -num1
num2 >= 0 and num2 or -num2
print["Hcf of", num1, "and", num2, "is", getHCF[num1, num2]]Output