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

Table of Contents

## 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…