;

# Python Program to Find the HCF or GCD

###### Tutorialsrack 22/04/2020 Python

In this Python program, we will learn how to find the HCF(Highest Common Factor) or GCD (Greatest Common Divisor). In this program, we will use two different methods to find the HCF or GCD: using Loops and Euclidean algorithm.

## What is HCF?

An HCF or GCD of two or more numbers is the largest positive integer that divides each of the numbers. For example, the HCF or GCD of 10 and 12 is 2.

Here is the code of the program to find the HCF(Highest Common Factor) or GCD (Greatest Common Divisor) using for loop.

### Program 1: Python program to find H.C.F of two numbers Using for Loop

##### Python program to find H.C.F of two numbers Using for Loop
``````# Python program to find H.C.F of two numbers Using for Loop

# define a 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

# To Take Input from the User
num1 = int(input("Enter the First Number: "))
num2 = int(input("Enter the Second Number: "))

print("\nThe H.C.F. is", compute_HCF(num1, num2))
``````
##### Output

Enter the First Number: 15

Enter the Second Number: 20

The HCF is 5

## Euclidean algorithm

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers) is the largest number that divides them both without a remainder.

The algorithm is based on the below facts:

If we divide the larger number by smaller number and take the remainder and now divide that smaller number by this remainder. Repeat until the remainder is equal to 0.

For example, if we want to find the H.C.F. of 60 and 36, we divide 60 by 36. The remainder is 24. Now, we divide 36 by 24 and the remainder is 12. Again, we divide the 24 by 12 and the remainder is 0. Hence, 12 is the required H.C.F.

### Program 2: Python program to find H.C.F of two numbers Using Euclidean algorithm

##### Python program to find H.C.F of two numbers Using Euclidean algorithm
``````# Python program to find H.C.F of two numbers Using Euclidean algorithm

# Function to find HCF the Using Euclidean algorithm
def compute_HCF(x, y):
while(y):
x, y = y, x % y
return x

# To Take Input from the User
num1 = int(input("Enter the First Number: "))
num2 = int(input("Enter the Second Number: "))

print("\nThe HCF is", compute_HCF(num1, num2))
``````
##### Output

Enter the First Number: 60

Enter the Second Number: 36

The H.C.F. is 12