Python program to find the greatest common factor (HCF) or greatest common divisor (GCD)

Python example in full

In this example, you will learn to find the GCD of two numbers using two different methods: function and loop, as well as the Euclidean algorithm

To understand this example, you should understand the followingPython programmingTopic:

• Python function

• Python recursion

• Python function parameters

The greatest common divisor (H.C.F) or greatest common factor (G.C.D) of two numbers is the largest positive integer that perfectly divides both given numbers. For example, H.C.F(12, 14) is equal to2。

Source code: Using a loop

# Python program to find the 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("H.C.F. is", compute_hcf(num1, num2))

Output result

H.C.F. is　6

Here, the variable num1and num2Two integers are passed to the compute hcf() function. The function calculates the H.C.F. of these two numbers and returns it.

In this function, we first determine the smaller of the two numbers, which can only be less than or equal to the smallest number. Then we use a for loop from1to that number.

In each iteration, we check if our number perfectly divides the two input numbers. If so, we store this number as H.C.F., and at the end of the loop, we get the largest number that perfectly divides the two numbers.

The above method is easy to understand and implement, but it is not efficient. A more efficient way to find HCF is the Euclidean algorithm.

Euclidean algorithm

This algorithm is based on the following fact: the HCF of two numbers will also divide their difference.

In this algorithm, we divide the larger number by the smaller number and then take the remainder. Now, divide the smaller number by this remainder. Repeat until the remainder is 0.

For example, if we want to find54and24hcf, we use54divided by24。The remainder is6。24divided by6，remainder is 0. Therefore,6is necessary hcf

Source code: Using Euclidean algorithm

# Function to find HCF using Euclidean 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 swaps the values in Python. Click here to learn more aboutSwapping variables in PythonMore information.

In each iteration, we place the value of y in x, and the rest (x % y) in y. When y becomes 0, we get the hcf of x.

Python example in full