Python Program to Find GCD or HCF

Summary: In this programming example, we will learn two ways to find the GCD of two numbers in Python.

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

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

Method 1: Using Loop

This method to find gcd using a loop in Python is a naive approach. In this method, we first find the smaller of the two numbers, then we loop from smaller to 1 in decreasing order and check it is a factor of both the numbers.

  1. Find the 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 by 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 work. It updates l to s and s to l%s.

These were the two ways using which we can easily compute the greatest common divisor of two numbers in Python.

Leave a Reply