# Python Program to Find HCF or GCD

Posted in  Vinay Khatri
Last updated on June 10, 2022

Here we have provided two python source code to find the GCD or HCF of two numbers.

### Prerequisite topics to create this program.

• Python Input, Output
• Python User-Defined Function
• Python Recursion
• Python if...else statements
• Python For loop

There are two common techniques we can use to find the HCF of two numbers, one is by using the function & loop and other is by using the Euclidean Algorithm HCF or GCD: HCF (Highest Common Factor) or GCD(Greatest Common Divisor) of two numbers is the largest positive integer which divides both the numbers perfectly. for example, the HCF of 6 and 9 is 3, because 3 is the largest number which can divide 9 and 6 completely. The HCF of two number always reside between the range of 1 to the smallest number. If there is no largest number which can divide both the numbers then the HCF of those two numbers is 1.

### HCF of two number using for loop

#### Steps:

• First, ask the user to enter the two numbers.
• Now using the comparison operator find the smaller number.
• Create a loop from 1 to the smallest number (included).
• using the comparison, arithmetic and logical operator we will find that number which can divide both the number perfectly.
• And if a number divides the both completely then that would be the HCF of both the number.

Code:

```def find_hcf(x, y):
# Find the smallest number
if x > y:
smallest = y
else:
smallest = x
for i in range(1, smallest+1):
if((x % i == 0) and (y % i == 0)):
hcf = i
return hcf

n1= int(input("Enter the First Number: "))
n2= int(input("Enter the Second Number: "))

print("The H.C.F. of", n1 ,"and",n2 ,"is:", find_hcf(n1, n2))```

Output 1:

```Enter the First Number: 54
Enter the Second Number: 24
The H.C.F. of 54 and 24 is: 6```

Output 2:

```Enter the First Number: 100
Enter the Second Number: 99
The H.C.F. of 100 and 99 is: 1```

### Find the HCF using Euclidean Algorithm:

In the Euclidean algorithm, we divide the larger number by the smaller number and calculate the remainder, then we divide the smaller number with the remainder, again calculate the remainder, and repeat this process until we get the remainder 0. for instance, if we want to find the HCF of 6 and 9, first we divide 9 with 6 because 9 is larger than 6, when we divide 9 by 6 we get 3 as a remainder, now using the remainder 3 we divide 6, and when we divide 6 by 3 we get 0 as a remainder which mean 3 is the HCF of 6 and 9. 9%6=3 6%3=0 HCF=3 steps:

• First, we will ask the user to enter two values.
• By using the comparison operator we will find the smaller number.
• Now start a while loop which continuously runs till the remainder get 0.
• Once the remainder is 0 we print the value of HCF.

Code:

```def find_hcf(x, y):
# Find the smallest number
if x > y:
smaller = y
larger=x
else:
smaller = x
larger=y
while(smaller):
smaller,larger = larger%smaller, smaller
return larger

n1= int(input("Enter the First Number: "))
n2= int(input("Enter the Second Number: "))

print("The H.C.F. of", n1 ,"and",n2 ,"is:", find_hcf(n1, n2))```

Output 1:

```Enter the First Number: 11
Enter the Second Number: 11
The H.C.F. of 11 and 11 is" 11```

Output 2:

```Enter the First Number: 50
Enter the Second Number: 55
The H.C.F. of 50 and 55 is: 5```