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:
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.
#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:
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
What did you think of this article? Have anything to add? Let’s discuss it in the comments below.