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

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

## 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

Hi, I'm Yagyavendra Tiwari, a computer engineer with a strong passion for programming. I'm excited to share my programming knowledge with everyone here and help educate others in this field.