## How to calculate HCF or GCD of two numbers in Python:

HCF(Highest common factor) or GCD(greatest common divisor) is the largest positive integer which can divide each of the numbers when at least one of the numbers is not zero.

For example, let’s find the HCF of *9* and *18*.
The divisors of *9* are *1, 3, 9* and the divisors of *18* are *1, 3, 6, 9*. So, the highest common factor or greatest common divisor of *9* and *18* is *9*.

We will learn different ways to find the *HCF* of two numbers in Python in this example.

### Method 1: Python program to find the HCF of two numbers by using a for loop:

In this example, we will use a for loop that will run from *1* to the smaller number. On each iteration, it will check if the current value of the loop can divide both the numbers or not. If yes, it will assign that value to a variable that will hold the *HCF* value once the loop ends.

Let’s write down the program:

```
def get_hcf(first, second):
smaller_no = first
if second < first:
smaller_no = second
hcf = 1
for i in range(2, smaller_no + 1):
if first % i == 0 and second % i == 0:
hcf = i
return hcf
n1 = int(input("Enter the first number: "))
n2 = int(input("Enter the second number: "))
print(f'HCF of {n1} and {n2} is: {get_hcf(n1, n2)}')
```

Here,

- It takes the numbers as inputs from the user and assigns to the
*n1*and*n2*variables. - The
*get_hcf*method is used to find the HCF of two numbers. It takes the numbers as its arguments and returns the*HCF*. - It assigns the smaller number to the
*smaller_no*variable. The*for loop*runs from*2*to*smaller_no*to find the HCF value. The HCF is assigned to the*hcf*variable.

If you run this program, it will print output as below:

```
Enter the first number: 13
Enter the second number: 52
HCF of 13 and 52 is: 13
Enter the first number: 12
Enter the second number: 46
HCF of 12 and 46 is: 2
```

### Method 2: Python program to find the HCF of two numbers by using a loop in reverse:

Instead of running a loop from *2* to the number, we can also run the loop in reverse, i.e. starting from the smaller number. Once we found any number, we can skip from the loop as that is the *HCF*.

This is a better approach than the previous one because it will reduce the number of loop steps.

Below is the complete program:

```
def get_hcf(first, second):
i = first
if second < first:
i = second
while (i > 0):
if first % i == 0 and second % i == 0:
return i
i = i - 1
n1 = int(input("Enter the first number: "))
n2 = int(input("Enter the second number: "))
print(f'HCF of {n1} and {n2} is: {get_hcf(n1, n2)}')
```

It will print similar output. In this program, *i* holds the smaller number and we are using a *while loop* instead of a *for loop*. The while loop will keep running until the value of *i* is greater than *0*. If any value of *i* can divide both *first* and *second*, it will return *i* i.e. this is the *HCF*.

### Method 3: Python program to find the HCF of two numbers by Euclid’s division algorithm:

Euclid’s division algorithm is an easy way to find the HCF of two numbers. The following steps we have to follow:

- Divide the greater number by the smaller number. Keep the remainder in a separate variable.
- Divide the smaller number by the remainder.
- Repeat the above two steps until the remainder become zero. The smaller number in the division will be the required
*HCF*.

Let’s write down the program:

```
def get_hcf(first, second):
while (second):
first, second = second, first % second
return first
n1 = int(input("Enter the first number: "))
n2 = int(input("Enter the second number: "))
print(f'HCF of {n1} and {n2} is: {get_hcf(n1, n2)}')
```

Let’s try to find the HCF of *14* and *76*:

*76/14*, remainder is*6*.*14/6*, remainder is*2*.*6/2*, remainder is*0*. So,*2*is the*HCF*.

### You might also like:

- Python program to check for Moran numbers
- Python program to check if a number is a perfect number or not
- 3 different Python programs to remove the first character of string
- Python assert statement explanation with examples
- 3 different Python programs to get a string after a substring
- Python example to print the function name as string with
`__name__`

and`__qualname__`

- Python program to check if a number is a Niven or Harshad number