Write a Python program to find the Highest Common Factor (HCF) or Greatest Common Divisor (GCD) of two numbers provided by the user. The HCF or GCD of two numbers is the largest number that divides both of them without leaving a remainder.

Input-Output Examples

Example 1:
Input:
Enter the first number: 54
Enter the second number: 24
Output:
The HCF (GCD) of 54 and 24 is: 6

Example 2:
Input:
Enter the first number: 81
Enter the second number: 27
Output:
The HCF (GCD) of 81 and 27 is: 27

Algorithm to find the HCF or GCD

1. Start
2. Take input: Prompt the user to enter two numbers.
3. Find the HCF using the Euclidean algorithm:
   • While the second number is not zero:
     • Set the first number to the second number.
     • Set the second number to the remainder of the division of the first number by the second number.
4. Display the result: The first number now holds the HCF (GCD).
5. End

Python Program to find the HCF or GCD

# Python program to find HCF or GCD of two numbers

# Function to find HCF using the Euclidean algorithm
def compute_hcf(x, y):
    while y != 0:
        x, y = y, x % y  # Continue until y becomes 0
    return x

# Take input from the user for two numbers
num1 = int(input("Enter the first number: "))
num2 = int(input("Enter the second number: "))

# Find the HCF of the two numbers
hcf = compute_hcf(num1, num2)

# Display the result
print(f"The HCF (GCD) of {num1} and {num2} is: {hcf}")

Code Explanation

1. Taking input from the user:
   The program uses the input() function to take two numbers from the user. The inputs are converted to integers using int().
2. Using the Euclidean algorithm to find the HCF:
   The Euclidean algorithm is an efficient method to compute the HCF (or GCD). The algorithm works by repeatedly replacing the larger number with the remainder of the division of the two numbers, until the remainder becomes zero. The last non-zero number is the HCF. This is implemented in the function compute_hcf().
3. Displaying the output:
   The print() function is used to display the HCF of the two numbers using an f-string to format the output clearly.