In this article, we will discuss how to write a Python program to find the Highest Common Factor (HCF) or Greatest Common Divisor (GCD) of two given numbers. We’ll be able to provide you with a step-by-step guide oncreatinge this program, along with some examples to show how it’s used.

What is HCF or GCD?

HCF, or GCD, is the largest positive integer that divides two or more numbers without leaving any remainder. For example, the HCF of 12 and 16 is 4 because 4 is the largest positive integer that divides 12 and 16 without leaving a rest. The HCF, or GCD is an essential concept in mathematics and is frequently used in many algorithms and applications.

Python Program to Find HCF or GCD

The Python program to find the HCF or GCD of two numbers can be easily implemented using the Euclidean algorithm. The Euclidean algorithm is a simple and efficient method to find the GCD of two numbers. The steps involved in the Euclidean algorithm are as follows:

  1. Take two numbers as input, say num1 and num2.
  2. Divide the larger and smaller numbers and find the remainder.
  3. Replace the larger number with the smaller number and the smaller number with the remainder obtained in step 2.
  4. Repeat steps 2 and 3 until the remainder becomes zero.
  5. The GCD of the two numbers is the last non-zero remainder obtained in step 2.

Let’s take an example to understand how the Euclidean algorithm works.

Writing a Python Program to Find HCF or GCD

To write a Python program to find the HCF or GCD of two numbers, we can use the Euclidean algorithm. Here is the Python program:

				
					# Function to find HCF or GCD of two numbers
def find_hcf(num1, num2):
    # Ensure that num1 is always greater than num2
    if num1 < num2:
        num1, num2 = num2, num1
        
    # Loop until num2 is not equal to 0
    while num2:
        num1, num2 = num2, num1 % num2

    # Return the HCF or GCD
    return num1

# Test the function
print(find_hcf(12, 18))  # Output: 6

In this program, we define a function called find_hcf that takes two parameters, num1, and num2. We first ensure that num1 is always greater than num2. Then, we use a while loop to repeatedly subtract the smaller number from the larger number until one of the numbers becomes zero. Finally, we return the HCF or GCD, the other number.

Finding the HCF or GCD of two numbers is a common mathematical problem that can be solved efficiently and reliably using a Python program. The Euclidean algorithm is the most common and efficient method to find the HCF or GCD of two numbers. We have provided a Python program that implements the Euclidean algorithm to find the HCF or GCD of two numbers. We hope that this article has been helpful in understanding how to write a Python program to find the HCF or GCD of two numbers.


Thanks for reading. Happy coding!