Python Program to Find HCF or GCD – 2024

Hey guys, in this blog we will see a Python Program to Find HCF or GCD.

Example 1: Using Loops

# Python Program to Find HCF or GCD

# define hcf 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 = int(input('Enter 1st number -> '))
num2 = int(input('Enter 2nd number -> '))

print("The H.C.F. is", compute_hcf(num1, num2))

Output

Enter 1st number -> 24
Enter 2nd number -> 24
The H.C.F. is 24

Enter 1st number -> 34
Enter 2nd number -> 24
The H.C.F. is 2

Enter 1st number -> 50
Enter 2nd number -> 100
The H.C.F. is 50

• Suppose we enter two numbers 12 and 24.
• It will traverse from 1 to 13 (12+1) and check with every number that both 12 and 24 are divisible by that number or not.
• If it is divisible, it will be the current HCF.
• The HCF for 12 and 24 will be 12 itself.

Example 2: Using Euclidean Algorithm

# Python Program to Find HCF or GCD Using Euclidean algorithm
def compute_hcf(x, y):
    while(y):
        x, y = y, x % y
    return x

hcf = compute_hcf(int(input("1st number -> ")), int(input("2nd number -> ")))
print("The HCF is", hcf)

Output

1st number -> 12
2nd number -> 4
The HCF is 4

1st number -> 23
2nd number -> 32
The HCF is 1

1st number -> 8884
2nd number -> 4448
The HCF is 4

Following is the Euclidean Algorithm to calculate the HCF of a number:

while(y):
        x, y = y, x % y
    return x

Check out our other python programming examples…