GCD of two numbers in Python

In the previous article, we explored two different approaches towards obtaining the factorial of a number. In this current article we will explore how we can obtain the GCD of two numbers in Python. The common divisor of several integers is a number that can be a divisor of each number in the specified set. For example, the numbers 12 and 8 have a common factor of four. The greatest common divisor of two numbers a and b is the largest number by which a and b are divisible without a remainder. However there are multiple various in which GCD is commonly derived or obtained.

Obtaining the GCD of two numbers in Python

Before we look at the program let us solve a problem, we are given a rectangular surface like the one in the image below. Our task is to completely fill the surface, using equal sized square tiles.

If we are using 1*1 size squares we would need 6*9 squares to fill up the rectangle that would result in 54 different square tiles. Could we will the rectangle with 2*2 squares. It would not be able to fill as the they wouldn’t fit within the confines of the last column. The question is how many squares of a particular size can be used to fill the rectangle completely? The answer is 3*3 and if we try it with any larger number it would not be able to fit the rectangle completely.

How can we arrive to a solution for this problem and for similar situations? The solution can be obtained through finding out the Greatest Common Divisor. Suppose we are given the numbers a=6, and b=9,like in the above problem the GCD would be 3. For the GCD of 10 and 15 it would be 5.

To implement a program that can obtain the GCD in Python, first we need to start the loop past 1 and run it to obtain the greatest common divisor which can completely divide both of any two given numbers. We can use the min( ) function to obtain the smallest of two or more numbers. The GCD of a number cannot be greater than the smallest of the two numbers.

a=int(input("Enter a"))
b=int(input(" Enter b"))
small=min(a,b)
 for i in range(1, small+1)
    if(a%i==0 and b%i==0)
        gcd=i
 print("GCD is ", gcd)

Output:
Enter a : 6
Enter b : 9
GCD is  3

The program prints out the resultant GCD of 6 and 9 as expected

Alternative method/program through the use of function

We can find out the GCD through a much simpler way through the use of the built in gcd function which comes as part of the math library package.

# Python code to demonstrate the working of gcd() 
# importing "math" library
import math
a=int(input("Enter a"))
b=int(input(" Enter b"))
print(math.gcd(a, b))

Output:
Enter a : 6
Enter b : 9
3

Thus, we have revised the concept of GCD, two ways in which we can write a program of GCD of two numbers in Python. In the next article we will explore LCM of two numbers in Python