Python Program to Find GCD or HCF

Write a program in python to find gcd of two numbers.

GCD or HCF of two numbers is the largest number which divides both the numbers. For example, GCD of 12 and 16 is 4.

There are two methods to find gcd of two numbers, let’s see both of them.

Method 1: Using Loop

This method to find gcd using loop in python is a naive approach. Basically we first smaller of the two numbers, then we loop from smaller to 1 in decreasing order.

1. Find smaller of the two numbers.
2. Loop from smaller to 1 in decreasing order and check if its divides both the numbers.
3. If yes then that number is the GCD.

Let’s see its implementation in Python.

print("Enter two numbers")
a = int(input())
b = int(input())

smaller = 0

#find smaller number
if a < b:
    smaller = a
else:
    smaller = b

#find the highest factor of a and b
for i in range(smaller, 0,-1):
    if (a%i == 0) and (b%i == 0):
        print("GCD: ",i)
        break

Output

Enter two numbers                                                                                                             
12                                                                                                                            
16                                                                                                                            
GCD:  4 

This method is not efficient for computing gcd. The second method which uses the Euclidean Algorithm is best for computing GCD.

Method 2: Using the Euclidean Algorithm

In this algorithm, we divide the larger number with the smaller and update the larger number to the smaller number and the smaller number to the remainder. We do this until we get the remainder as zero and the final value of the larger number will be the gcd.

Let's see its implementation in Python code.

def findGCD(l, s):
    while(s):
        l, s = s, l%s
    return l
    
print("Enter two numbers")
a = int(input())
b = int(input())

print("GCD: ",findGCD(a,b))

Output

Enter two numbers                                                                                                             
50                                                                                                                            
10                                                                                                                            
GCD:  10

In the above program l, s = s, l%s does the swapping/updation work. It update l to s and s to l%s.

If you have any doubts or suggestion then comment below.