Python Program to Find GCD of Two Numbers

Last Updated on November 23, 2023 by Ankit Kochar

Python is a versatile programming language known for its simplicity and readability. It provides numerous built-in functions that make complex tasks easy to implement. One such essential computation is finding the Greatest Common Divisor (GCD) of two numbers. The GCD is the largest positive integer that divides both numbers without leaving a remainder. This article explores a Python program to efficiently calculate the GCD using different methods and discusses its significance in various mathematical and computational contexts.

This Python script utilizes the Euclidean Algorithm to efficiently compute the GCD of two inputted numbers. The algorithm involves repeatedly replacing the larger number with the remainder of the division of the larger number by the smaller number until the smaller number becomes zero. The GCD is then the last non-zero remainder obtained.

What is GCD?

The greatest common divisor (GCD) is the largest positive integer that divides two numbers without leaving any remainder. It is a fundamental concept in number theory and has applications in various mathematical and programming problems. In this article, we will explore how to write a Python program to find the GCD of two numbers using different approaches.

Methods of Python Program to Find GCD of two numbers

There are 5 different methods of Python program to find GCD of two numbers:

• Method 1: Linear Quest to find GCD
• Method 2: Euclidean Algorithm: Repeated Subtraction
• Method 3: Recursive Euclidean Algorithm: Repeated Subtraction
• Method 4: Modulo Recursive Euclidean Algorithm: Repeated Subtraction
• Method 5: Handling Negative Numbers in GCD

Method 1: Linear Quest

Algorithm to find GCD of two numbers using Linear Quest

• Initialize GCD = 1
• Run a loop in the iteration of (i) between [1, min(num1, num2)]
• Note down the highest number that divides both num1 & num2
• If i satisfies (num1 % i == 0 and num2 % i == 0) then new value of GCD is i
• Print value of GCD

Code Implementation

num1 = 36
num2 = 60
gcd = 1
 
for i in range(1, min(num1, num2)):
    if num1 % i == 0 and num2 % i == 0:
        gcd = i
print("GCD of", num1, "and", num2, "is", gcd)

Output

GCD of 36 and 60 is 12

Method 2: Repeated Subtraction

Algorithm to find GCD of two numbers using Repeated Subtraction

• Run a while loop until num1 is not equal to num2
• If num1>num2 then num1 = num1 – num2
• Else num2 = num2 – num1
• After the loop ends both num1 & num2 stores GCD

Code Implementation

num1 = 36
num2 = 60
a = num1
b = num2

while num1 != num2:
    if num1 > num2:
        num1 -= num2
    else:
        num2 -= num1

print("GCD of", a, "and", b, "is", num1)

Output:

GCD of 36 and 60 is 12

Method 3: Repeated Subtraction using Recursion

Algorithm to find GCD of two numbers using Repeated Subtraction using recursion

• Checked whether any of the input is 0 then return the sum of both numbers
• If both inputs are equal return any of the two numbers
• If num1 is greater than the num2 then Recursively call findGCD(num1 – num2, num2)
• Else Recursively call findGCD(num1, num2-num1)

Code Implementation

# Recursive function to return GCD of two number
def findGCD(num1, num2):
    
    # Everything divides 0
    if num1 == 0 or num2 == 0:
        return num1 + num2
    
    # base case
    if num1 == num2:
        return num1
    
    # num1>num2
    if num1 > num2:
        return findGCD(num1 - num2, num2)
    else:
        return findGCD(num1, num2 - num1)


num1 = 36
num2 = 60

print("GCD of", num1, "and", num2, "is", findGCD(num1, num2))

Output

GCD of 36 and 60 is 12

Method 4: Repeated Subtraction with Modulo Operator using Recursion

Algorithm to find GCD of two numbers using Repeated Subtraction with Modulo Operator using Recursion

Algorithm is as follows:

• If b is equal to 0 return a
• Else recursively call the function for value b, a%b, and return

Code Implementation

# This method improves complexity of repeated subtraction
# By efficient use of modulo operator in euclidean algorithm
def getGCD(a, b):
    return b == 0 and a or getGCD(b, a % b)


num1 = 36
num2 = 60

print("GCD of", num1, "and", num2, "is", getGCD(num1, num2))

Output:

GCD of 36 and 60 is 12

Method 5: Handling Negative Numbers in GCD

Algorithm to find GCD of two numbers using Handling Negative Numbers in GCD

If any of the numbers is negative then convert it to positive by multiplying it with -1 as according to the proper definition GCD of two numbers can never be negative.

• If b is equal to 0 return a
• Else recursively call the function for value b, a%b, and return

Code Implementation

# This method improves complexity of repeated subtraction
# By efficient use of modulo operator in Euclidean algorithm
def getGCD(a, b):
    return b == 0 and a or getGCD(b, a % b)


num1 = -36
num2 = 60

# if user enters negative number, we just changing it to positive
# By definition GCD is the highest positive number that divides both numbers
# -36 & 60 : GCD = 12 (as highest num that divides both)
# -36 & -60 : GCD = 12 (as highest num that divides both)
num1 >= 0 and num1 or -num1
num2 >= 0 and num2 or -num2

print("GCD of", num1, "and", num2, "is", getGCD(num1, num2))

Output

GCD of 36 and 60 is 12

Conclusion
The ability to find the Greatest Common Divisor (GCD) of two numbers is fundamental in various mathematical and computational applications. Python’s simplicity and flexibility empower programmers to implement efficient algorithms, such as the Euclidean Algorithm, to compute the GCD effortlessly. Whether in cryptography, number theory, or simplifying fractions, knowing how to determine the GCD is invaluable in problem-solving and algorithmic development.

FAQs related to Python program to find GCD of two numbers

Here are some FAQs related to find GCD of Two Numbers.

1. What is the significance of finding the GCD of two numbers?
The GCD helps in simplifying fractions, solving modular arithmetic problems, implementing cryptographic algorithms, and more. It is essential in various mathematical computations and has practical applications in computer science.

2. Are there other methods to find the GCD apart from the Euclidean Algorithm?
Yes, there are various methods like the prime factorization method, using the Stein algorithm, or utilizing the math library’s built-in functions in Python.

3. Can the GCD of more than two numbers be calculated using this Python program?
The provided Python script calculates the GCD of two numbers. To find the GCD of multiple numbers, you can repeatedly calculate the GCD of pairs of numbers iteratively.

4. How efficient is the Euclidean Algorithm in finding the GCD?
The Euclidean Algorithm is highly efficient and has a time complexity of O(log(min(a, b))), where a and b are the input numbers. It’s one of the most commonly used methods due to its speed and simplicity.