Write a Program to Find GCD of Two Numbers

What is GCD (Greatest Common Divisor)?

GCD of the two numbers is the largest positive integer that divides both numbers.

Characteristics:

• The GCD of the two numbers is always lesser than two numbers or equal to the smaller number.
• GCD of two numbers can never be greater than both numbers.
• GCD of the two prime numbers is one.

Example:

• GCD of the 10 and 5 is 5 (As 10 is divisible by 5.)
• GCD of the 90 and 48 is 6.

Program to Find the GCD of Two Numbers

There are many interviews where this question has been asked. This has been asked in Kirloskar Technical interview round.

Here we are using recursion.

Algorithm:

1. Divide the number ‘a’ by ‘b’ and get the reminder.
2. If the remainder is zero (the number ‘a’ is divisible by the number ‘b’), return ‘b’ (GCD of the two numbers is ‘b’).
3. Else, assign a=b and b=a%b. Call step 1 recursively.

Python code:

def gcd(a, b):
    if a%b==0:
        return b
    return gcd(b, a%b)

print(gcd(8, 6))
print(gcd(45, 12))
print(gcd(120, 46))

Output:

2
3
24

This small function can be very much handy for solving Python competitive coding questions.

This is the simplest solution and program to find GCD of two numbers.

Aniruddha Chaudhari

I am complete Python Nut, love Linux and vim as an editor. I hold a Master of Computer Science from NIT Trichy. I dabble in C/C++, Java too. I keep sharing my coding knowledge and my own experience on <b>CSEstack.org</b> portal.