Python Program to Find GCD of Two Numbers

Last Updated on May 31, 2023 by Prepbytes

Finding the GCD is a common task in various mathematical and programming problems. It has applications in simplifying fractions, finding the least common multiple (LCM), prime factorization, and more. Python provides built-in functions and algorithms that simplify the process of finding the GCD.

By the end of this article, you will have a clear understanding of how to find the GCD of two numbers in Python, enabling you to apply this knowledge to solve various mathematical and programming challenges effectively.

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
In this article, we explored two different methods to find the greatest common divisor (GCD) of two numbers in Python. The first method involved implementing the Euclidean algorithm manually, while the second method utilized the built-in gcd() function from the math module. Both methods are effective and can be used based on your specific requirements. The GCD is a fundamental concept in number theory and finding it is often a crucial step in solving various mathematical and programming problems.

FAQs related to Python program to find GCD of two numbers

Q1: What is the Euclidean algorithm?
Ans. The Euclidean algorithm is an efficient method for finding the GCD of two numbers. It is based on the principle that the GCD of two numbers is the same as the GCD of the smaller number and the remainder of the larger number is divided by the smaller number. The algorithm repeatedly replaces the larger number with the remainder until the remainder becomes zero, at which point the GCD is found.

Q2: What is the gcd() function in Python’s math module?
Ans. The gcd() function is a built-in function in Python’s math module. It calculates the GCD of two numbers using an optimized algorithm. By utilizing this function, you can simplify your code and avoid manually implementing the GCD calculation.

Q3: Can I find the GCD of more than two numbers?
Ans. Yes, you can extend the code to find the GCD of more than two numbers. One approach is to find the GCD of the first two numbers, then calculate the GCD of that result and the next number, and so on. You can either modify the Euclidean algorithm code or use the gcd() function iteratively to achieve this.

Q4: What happens if one or both of the input numbers are negative?
Ans. The GCD is always positive, regardless of the signs of the input numbers. Therefore, if one or both of the input numbers are negative, you can take their absolute values (using the abs() function) before finding the GCD to ensure consistent results.

Q5: Are there any other algorithms to find the GCD?
Ans. Yes, apart from the Euclidean algorithm, there are other algorithms to find the GCD, such as the Binary GCD algorithm and the Extended Euclidean algorithm. The Euclidean algorithm is the most commonly used and efficient for finding the GCD of two numbers, but depending on the specific requirements or constraints of your problem, you may explore these alternative algorithms as well.