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

Abhishek Sharma
Abhishek Sharma

Started my Data Science journey in my 2nd year of college and since then continuously into it because of the magical powers of ML and continuously doing projects in almost every domain of AI like ML, DL, CV, NLP.

Articles: 517

Leave a Reply

Your email address will not be published. Required fields are marked *