Python program to find the HCF or GCD of 2 numbers

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