1. Home

Python Tutorials - Elevate Your Coding Skills with Comprehensive Tutorials

Discover Python tutorials covering everything from the basics to advanced topics. Whether you're new to programming or looking to level up your skills, our tutorials will guide you every step of the way

• 201 Lessons
• 33 Hours
127

# GCD of Two Numbers in Python

Updated on 19/07/20245,608 Views

## Introduction

The concept of the Greatest Common Divisor (GCD) transcends mere mathematical theory, finding its place in practical problem-solving across various fields. In computer science, it optimizes algorithms and plays a significant role in time complexity. Python, with its renowned adaptability, offers numerous methods to calculate the GCD, providing accessible tools for both mathematicians and programmers. In this article, we will explore these methods, offering explanations and real-world examples to guide you in finding the GCD of two numbers in Python. Whether you're a student eager to delve into mathematical fundamentals or a programmer looking to refine your problem-solving skills, understanding the GCD and Python's array of calculation techniques unfurls ways to new learning possibilities.

## Overview

The Greatest Common Divisor (GCD) is a mathematical concept representing the largest number that divides two given integers without leaving a remainder. Calculating the GCD of two numbers is a common task in many mathematical and computer science applications. In Python, there are several methods to GCD of two numbers in Python, including using the Standard Template Library (STL), recursion, the Euclidean Algorithm, and Lambda functions.

## Python Program to Find the GCD of Two Numbers Using STL

The Standard Template Library (STL) is not a part of Python; it's a C library. You'd need to utilize a C library or interface it with Python through tools like Boost to use it in Python. However, you can easily find the GCD of n numbers in Python using the built-in math library with the math.gcd() function works as follows:

• 1: Import the math library:

code

`Import math`
• 2: Input two numbers that you want to find the GCD of.
• 3: Use the math.gcd() function to calculate the GCD:

Python code

`gcd = math.gcd(num1, num2)`
• 4: Print the GCD:
`print(f"GCD of {num1} and {num2} is {gcd}")`

Here's an example:

Python code

`# Import the math libraryimport math# Define the two numbersnum1 = 48num2 = 18# Calculate the GCD using math.gcd()gcd = math.gcd(num1, num2)# Print the resultprint(f"GCD of {num1} and {num2} is {gcd}")`

Output:

GCD of 48 and 18 is 6

In this example, we first import the math library and then define two numbers, num1 and num2. We calculate the GCD using math.gcd() function and display the result, which is 6 in this case.

## Python Program to Find the GCD of Two Numbers Using Recursion

Calculating the GCD of n numbers in Python using recursion is a common mathematical approach. We can implement this by defining a recursive function that applies the Euclidean Algorithm.

Here are the steps to find the GCD of two numbers using recursion:

• Define a recursive function that takes two arguments, a and b.
• In the function, use the Euclidean Algorithm:
• If b is 0, return a as the GCD.
• Otherwise, call the function recursively with arguments b and a % b.
• Input two numbers that you want to find the GCD of.
• Call the recursive function with these two numbers to calculate the GCD.
• Print the GCD.

Here are the examples:

Example 1:

Python code

`def gcd_recursive(a, b):    if b == 0:        return a    return gcd_recursive(b, a % b)num1 = 48num2 = 18gcd = gcd_recursive(num1, num2)print(f"GCD of {num1} and {num2} is {gcd}")`

Output:

GCD of 48 and 18 is 6

In this example, we define a gcd_recursive function that takes two arguments, a and b. It uses the Euclidean Algorithm recursively to calculate the GCD. We then call the function with the numbers 48 and 18 and print the result.

Example 2:

Python code

`def gcd_recursive(a, b):    if b == 0:        return a    return gcd_recursive(b, a % b)num1 = 35num2 = 14gcd = gcd_recursive(num1, num2)print(f"GCD of {num1} and {num2} is {gcd}")`

Output:

GCD of 35 and 14 is 7

Here, we use the same gcd_recursive function to find the GCD of 35 and 14, resulting in a GCD of 7.

Example 3:

Python code

`def gcd_recursive(a, b):    if b == 0:        return a    return gcd_recursive(b, a % b)num1 = 77num2 = 22gcd = gcd_recursive(num1, num2)print(f"GCD of {num1} and {num2} is 11")`

Output:

GCD of 77 and 22 is 11

This example demonstrates how the recursive function can be used to find the GCD of 77 and 22, which is 11.

Example 4:

Python code

`def gcd_recursive(a, b):    if b == 0:        return a    return gcd_recursive(b, a % b)num1 = 12num2 = 18gcd = gcd_recursive(num1, num2)print(f"GCD of {num1} and {num2} is {gcd}")`

Output:

GCD of 12 and 18 is 6

Here, the same gcd_recursive function is used to calculate the GCD of 12 and 18, resulting in a GCD of 6.

## Find the GCD of two Numbers in Python Using the Euclidean Algorithm

The Euclidean Algorithm is an efficient method to calculate the GCD of two numbers in Python. It involves iteratively applying the modulo operation.

Here are the steps to find the GCD of two numbers in Python using the Euclidean algorithm:

• Input two numbers, a and b.
• Use a while loop to implement the Euclidean Algorithm:
• Inside the loop, calculate the remainder of a divided by b and store it in a temporary variable.
• Update a with the value of b and b with the value of the temporary variable.
• Repeat the loop until b becomes 0.
• The value of a at the end of the loop will be the GCD of the two numbers.
• Print the GCD.

Here is the gcd of two numbers in Python using Euclidean algorithm examples:

Example 1:

Python code

`def euclidean_gcd(a, b):    while b:        a, b = b, a % b    return anum1 = 48num2 = 18gcd = euclidean_gcd(num1, num2)print(f"GCD of {num1} and {num2} is {gcd}")`

Output:

GCD of 48 and 18 is 6

In this example, we define the euclidean_gcd function, which uses the Euclidean Algorithm to calculate the GCD. We then call the function with the numbers 48 and 18 and display the result.

Example 2:

Python code

`def euclidean_gcd(a, b):    while b:        a, b = b, a % b    return anum1 = 35num2 = 14gcd = euclidean_gcd(num1, num2)print(f"GCD of 35 and 14 is 7")`

Output:

GCD of 35 and 14 is 7

Here, the same euclidean_gcd function is used to find the GCD of 35 and 14, resulting in a GCD of 7.

Example 3:

Python code

`def euclidean_gcd(a, b):    while b:        a, b = b, a % b    return anum1 = 77num2 = 22gcd = euclidean_gcd(num1, num2)print(f"GCD of 77 and 22 is 11")`

Output:

GCD of 77 and 22 is 11

This example demonstrates how the euclidean_gcd function can be used to find the GCD of 77 and 22, which is 11.

Example 4:

Python code

`def euclidean_gcd(a, b):    while b:        a, b = b, a % b    return anum1 = 12num2 = 18gcd = euclidean_gcd(num1, num2)print(f"GCD of 12 and 18 is 6")`

Output:

GCD of 12 and 18 is 6

In this example, the euclidean_gcd function calculates the GCD of 12 and 18, resulting in a GCD of 6.

## Find GCD with Lambda Function

Lambda functions in Python provide a concise way to define small, anonymous functions. We can use a lambda function to calculate the GCD of two numbers and the GCD of three numbers in Python.

Steps to find GCD with Lambda Function:

• Define a lambda function that takes two arguments, a and b.
• Use the lambda function to calculate the GCD:
• The lambda function should implement the Euclidean Algorithm as a recursive call.
• Input two numbers that you want to find the GCD of.
• Call the lambda function with these two numbers to calculate the GCD.
• Print the GCD.

Here are the examples:

Example 1:

Python code

`gcd = lambda a, b: a if not b else gcd(b, a % b)num1 = 48num2 = 18result = gcd(num1, num2)print(f"GCD of {num1} and {num2} is {result}")`

Output:

GCD of 48 and 18 is 6

In this example, we define a lambda function gcd that takes two arguments, a and b. It uses the Euclidean Algorithm to calculate the GCD and then calls the lambda function with the numbers 48 and 18, displaying the result.

Example 2:

Python code

`gcd = lambda a, b: a if not b else gcd(b, a % b)num1 = 35num2 = 14result = gcd(num1, num2)print(f"GCD of 35 and 14 is 7")`

Output:

GCD of 35 and 14 is 7

Here, the lambda function is used to find the GCD of 35 and 14, resulting in a GCD of 7.

Example 3:

Python code

`gcd = lambda a, b: a if not b else gcd(b, a % b)num1 = 77num2 = 22result = gcd(num1, num2)print(f"GCD of 77 and 22 is 11")`

Output:

GCD of 77 and 22 is 11

This example demonstrates how the lambda function can be used to find the GCD of 77 and 22, which is 11.

Example 4:

Python code

`gcd = lambda a, b: a if not b else gcd(b, a % b)num1 = 12num2 = 18result = gcd(num1, num2)print(f"GCD of 12 and 18 is 6")`

Output:

GCD of 12 and 18 is 6

In this example, the lambda function calculates the GCD of 12 and 18, resulting in a GCD of 6.

## Conclusion

In exploring Python's capabilities for calculating the Greatest Common Divisor (GCD), we've uncovered a wealth of methods for diverse preferences and applications. The math library offers simplicity, recursion brings algorithmic precision, the Euclidean Algorithm provides efficiency, and lambda functions ensure concise code. The GCD, a fundamental mathematical concept, is not limited to theory; it simplifies fractions, optimizes algorithms, and solves practical problems. Python's proficiency in GCD calculations positions it as a valuable asset for students, programmers, and professionals, empowering them to tackle various mathematics and computer science challenges. You can master the GCD of two numbers in Python methods to expand your problem-solving toolkit, learn how to find the GCD of three numbers in Python and deepen your understanding of the GCD's importance in different applications.

## FAQs

Q1. What is the Greatest Common Divisor (GCD)?

The Greatest Common Divisor (GCD) of two numbers is the largest positive integer that divides both numbers without leaving a remainder. It is also known as the greatest common factor or highest common factor.

Q2. Why is the GCD important in mathematics and computer science?

The GCD is important because it has various applications in number theory, cryptography, algorithm design, and more. It is often used to simplify fractions, find common factors in mathematical problems, and optimize algorithms for efficiency.

Q3. When should I use recursion to find the GCD?

Recursion is useful for finding the GCD when you prefer a more mathematical and algorithmic approach. The Euclidean Algorithm, which involves recursion, is one of the most efficient methods for GCD calculations.

Q4: When should I use recursion to find the GCD?

Recursion is suitable for finding the GCD when you want an algorithmic and mathematically elegant approach. The Euclidean Algorithm, which is often implemented using recursion, is highly efficient.

Q5: Can you use lambda functions to find the GCD in Python?

Yes, you can use lambda functions in Python to calculate the GCD of two numbers. Lambda functions concisely define small, anonymous functions for simple mathematical operations like GCD calculations.

Director of Engineering

Director of Engineering @ upGrad. Motivated to leverage technology to solve problems. Seasoned leader for startups and fast moving orgs. Working …Read More

###### Get Free Career Counselling
+91
*
By clicking, I accept theT&Cand
Join 10M+ Learners & Transform Your Career
Learn on a personalised AI-powered platform that offers best-in-class content, live sessions & mentorship from leading industry experts.

Talk to our experts. We’re available 24/7.

Indian Nationals

1800 210 2020

Foreign Nationals

+918045604032

## Disclaimer

upGrad does not grant credit; credits are granted, accepted or transferred at the sole discretion of the relevant educational institution offering the diploma or degree. We advise you to enquire further regarding the suitability of this program for your academic, professional requirements and job prospects before enr...