How to Find GCD of Two Numbers in Python

In this post, we will learn how to find GCD of two numbers in Python with detailed explanation and example.

But before we jump into programming part first let’s understand a mathematical approach to find the GCD of two numbers.

Find GCD of two numbers

Suppose you have two numbers, 12 and 30, and you want to calculate the GCD/HCF of these two numbers. The first step is to find the factors of both numbers, and the final step is to identify the highest common number among the factors of both numbers.

Here 6 is the highest and common in both so 6 is a GCD of 12 and 30.

Now we know a mathematical approach to calculate a GCD/HCF of two numbers.

So now, let’s see how we can implement it in Python. From the above explanation and example, we know that the GCD of two numbers is always less than or equal to the smaller of the two given numbers. So, we will iterate from 1 to that smaller number and check if any number can divide both given numbers evenly. Then we will assume that the number is our GCD, and at the end of the iteration, we will have found our actual GCD.

For your better understanding let’s see the algorithm and then write a code based on the algorithm.

Algorithm

1	Define a function that takes two argument (def find_GCD(n1,n2))
2	Identify the smaller number from n1 & n2 using an if-else statement and store it in a variable called smaller.
3	Using for-loop iterate form 1 to a smaller number (for i in range(1,smaller+1))
4	Inside for-loop check if (n1%i == 0 and n2%i == 0) then store i in variable called gcd
5	Outside of the for-loop return gcd

Now we are all set to write a code but before we write a code few programming concepts you have to know:

1. Python Functions
2. for-loop &
3. if-else statements

Source Code

def find_GCD(n1,n2):
    if n1 < n2:
        smaller = n1
    else:
        smaller = n2
    
    for i in range(1,smaller+1):
        if (n1%i == 0 and n2%i == 0):
            gcd = i
    
    return gcd


num1 = int(input("Enter number-1: "))
num2 = int(input("Enter number-2: "))


print(f"GCD/HCF of {num1} & {num2} is {find_GCD(num1,num2)}")

Output-1

Enter number-1: 12
Enter number-2: 30
GCD/HCF of 12 & 30 is 6

Output-2

Enter number-1: 15
Enter number-2: 24
GCD/HCF of 15 & 24 is 3

We can also find the GCD/HCF of two numbers using the built-in function.

Find GCD of two numbers Using Built-in Function

The math module includes a function called math.gcd() that helps us find the greatest common divisor (GCD) of two or more integers.

import math

n1 = 15
n2 = 35

print(f"GCD of {n1} & {n2} is {math.gcd(n1,n2)}")

#Output: GCD of 15 & 35 is 5

👉 Related article: Find Factors of a Number in Python