How To Find The GCD Of Two Integers In Python

Last updated: March 31, 2018 at 22:38 pm
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
#It will then output 7

2. Finding The GCD OF 2 Integers Using A Python Script 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.

I explain how the algorithm works in the program’s comments.

Note: I wrote this script using python3. Here you can download the script I wrote.
To use it, import the file by doing
import gcd_function
or just edit the python file directly

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

import gcd_function

What did you think of this? Let’s discuss it in the comments below.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.