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