How To Find The GCD Of Two Integers In Python


Finding the greatest common divisor (gcd) of two numbers is incredibly useful in math and computer science. The gcd of two integers is the largest integer that divides evenly into both integers with no remainder. There are a multitude of applications for being able to find the gcd of two integers. Here, I will discuss two ways to find the gcd of 2 numbers.

1. Finding The GCD OF 2 Integers Using Python Native Modules

Python in fact has a native function called gcd from the module math. To use this function, in your shell or python file, first do the following. At the beginning of your file or in the shell type:
import math

Then, the usage of the python gcd function is
math.gcd(a,b) #where a and b are two different #integers.

Here is an example of how to use it for finding the gcd of the integers 7 and 21.
import math
math.gcd(7,21)
#It will then output 7

2. Finding The GCD OF 2 Integers Using A Python Script linuxwebdevelopment.com wrote

I personally like actually understanding functions by programming them myself, if at all possible. That is why I like writing them myself even if there are libraries out there, just for improving my own knowledge. I wrote a simple python program finding the gcd of 2 integers using the Euclidean Algorithm.

Note: I wrote this script using python3. Here you can download the script gcd_function.py I wrote.

def gcd(x,y):
    # if y > x, then switch them
    if (y > x):
        temp1 = y
        y = x
        x = temp1

    # edge cases. If x or y are negative, if one or both of them is
    # a 0, or if they are the same number.
    if (x == 0 and y == 0):
        return 1
    if (x == 0):
        return y
    if (y == 0):
        return x
    if (x < 0): 
        x = -x
    if (y < 0): y = -y if (x == y): return x # Using the Euclidean algorithm with x being the divisor and y # being the remainder for each step after the first step while (y > 0):
        temp2 = y
        y = x % y
        x = temp2

    # return the divisor when the remainder is 0
    return x

If you are downloading the file, you go to where the file is, then import the function with the following:
import gcd_function
Or just copy my Python code into a Python shell.

Here is the usage if you want to import it into the shell or into another file.
gcd_function.gcd(a,b) #will output the gcd of two integers a and #b

#example
gcd_function.gcd(8,2)
2

Want to know how to calculate the gcd of two integers in other languages? See how to do it in Javascript, and how to do it in PHP.

What did you think of this article? Have anything to add? Let’s discuss it in the comments below.

Leave a Reply