# Python program to find the HCF or GCD of 2 numbers

Learn how to find the highest common factor(HCF) or greatest common divisor(GCD) of 2 numbers in Python.

## Method 1

Let’s say you want to find the HCF of 8 and 20.

Step 1

Take the smallest number. In this case, the smallest number is 8.

Step 2

Divide the smallest number by all the numbers from 1 to that number itself and check for numbers that properly divide the smallest number with remainder 0. Those numbers are called Factors.

``````8 / 1 --> Divisible
8 / 2 --> Divisible
8 / 3 --> Not Divisible
8 / 4 --> Divisible
8 / 5 --> Not Divisible
8 / 6 --> Not Divisible
8 / 7 --> Not Divisible
8 / 8 --> Divisible``````

1, 2, 4 and 8 are factors of 8.

Step 3

Divide the largest number with the factors of the smallest number. The largest factor that divides the largest number with remainder 0, is the HCF.

``````20 / 1 = 20
20 / 2 = 10
20 / 4 = 5 <-- HCF is 4
20 / 8 --> Not Divisible``````

The HCF of 8 and 20 is 4.

## Method 2 - Using for loops

Code

``````num1 = 8
num2 = 20

smallest_num = min(num1, num2)
largest_number = max(num1, num2)
factors = []
hcf = None

for i in range(1, smallest_num+1):
if smallest_num%i == 0:
factors.append(i)

print(factors) # This should be in ascending order

for factor in factors:
if largest_number%factor == 0:
# Keep re-assigning the variable
# with bigger factor
hcf = factor

print(hcf)``````

Output

``````[1, 2, 4, 8]
4``````