Skip to main content

How to calculate the greatest common divisor (GCD) of two numbers in Python

How to calculate the greatest common divisor (GCD) of two numbers in Python.

Here is a step-by-step tutorial on how to calculate the greatest common divisor (GCD) of two numbers in Python.

Step 1: Understanding the concept of GCD​

The greatest common divisor (GCD) is the largest positive integer that divides two or more numbers without leaving a remainder. It is commonly used in various mathematical and programming applications.

Step 2: Importing the math module (if needed)​

Python has a built-in math module that provides several mathematical functions, including a function to calculate the GCD. If you want to use this built-in function, you need to import the math module by adding the following line at the beginning of your code:

import math

Step 3: Implementing the GCD algorithm​

There are multiple algorithms to calculate the GCD, but one of the most commonly used algorithms is the Euclidean algorithm. Let's implement this algorithm in Python.

def gcd(a, b):
    while b != 0:
        temp = b
        b = a % b
        a = temp
    return a

In the above code, we define a function gcd that takes two parameters a and b. Inside the function, we use a while loop to continue the calculations until b becomes zero. In each iteration, we update the values of a and b according to the Euclidean algorithm. Finally, we return a, which will be the GCD of the two numbers.

Step 4: Using the GCD function​

Now that we have implemented the GCD algorithm, we can use the gcd function to calculate the GCD of any two numbers.

# Example usage
num1 = 24
num2 = 36
result = gcd(num1, num2)
print("The GCD of", num1, "and", num2, "is", result)

In the above code, we assign two numbers (num1 and num2) and call the gcd function with these numbers as arguments. The returned value is stored in the result variable. Finally, we print the result using the print function.

Step 5: Handling negative numbers​

The above implementation works fine for positive numbers. However, if you want to handle negative numbers as well, you can modify the gcd function as follows:

def gcd(a, b):
    a = abs(a)
    b = abs(b)
    while b != 0:
        temp = b
        b = a % b
        a = temp
    return a

In the modified code, we use the abs function to convert the input numbers (a and b) into their absolute values before performing the calculations. This ensures that negative numbers are also handled correctly.

And that's it! You now have a step-by-step tutorial on how to calculate the greatest common divisor (GCD) of two numbers in Python.