GCD in Python

Greatest Common Divisor abbreviated as GCD is a very common term in Mathematics. For a set of two or more non zero integer values, the highest value of the common divisor is termed as their GCD. In alternate terms, the Greatest Common Divisor (GCD) is also known by the following names :

• Highest Common Factor – HCF
• Greatest Common Factor – GCF
• Highest Common Divisor – HCD
• Greatest Common Measure – GCM

The GCD concept finds application in a large range of different scenarios and specifically in the area of encryption and decoding. Sometimes it is also used for the very smallest of purposes like simplification of the numerator and denominator portions which are present infractions.

For anyone who knows the basics of mathematics, knowledge about GCD is common. Python language is known for encompassing various mathematical concepts and calculations by the means of predefined written code which are encapsulated as methods or functions, which can be fetched by importing the specific packages. Calculating the value of Greatest Common Divisor can be performed using the function Math.gcd() available under Math Module in Python programming language to make computations faster, accurate and precise.

Method 1: By the means of using Recursion

In this method of deriving the Greatest common divisor, we use the concept of recursion for deriving the desired results.

def gcd (m, n)
if ( n == 0)
return m
else:
return gcd (n, m%n)
print (“End result is : ”)
print ( gcd (100, 50))

Result

End result is : 10

Method 2: By the means of using loop structures

In this method, we deploy iterations and loop concepts to derive the Greatest common divisor of two numbers.

def getGCD (m, n)
if m > n
less = n
else :
less = m
for m in range (1, less+1)
if (m % a == 0) and (n % b ==0)) :
gcd = a
return gcd
print (“The final result is : “)
print ( getGCD (100, 50))

Result

The final result is : 10

Method 3: By the means of the Euclidean Algorithm

The Euclidean Algorithm is solely focused on the base concept that the GCD of two non zero, positive integer numbers will be capable of dividing the difference between the two numbers as well.

Now going ahead to see the logic of the program, we note that when we divide the larger number by the smaller number, we get a remainder value. Going forth, we now divide the smaller number by the residue reminder. One should keep iterating the same procedure in continuous cycles up until the point where the final reminder becomes zero.

def getGCD (k, l):
while (l) :                   
return k
print (“The final result is : “)
print (getGCD (100, 50))

Result

The final result i s : 10

Now that you have seen different methods of writing code for deriving the GCD of two numbers in Python, finally, we introduce you to the simplest Math function that can calculate the GCD in a single line of code.

But for this, you have to import the Math package in order to be able to use all the methods and functions that are available under the specific package. The method called gcd() can be used in order to derive and compute the GCD value of any two integers and return an integer value that gives the final output result. You can see the following program sample to have a clearer picture.

Let us see the working of math.gcd() function.

Syntax to be followed :

math.gcd (m,n)

Meaning of sample parameters

m – First non zero integer value for which GCD is going to be calculated

n – Second non zero integer value for which GCD is going to be calculated

Result

The math.gcd() method returns the highest value of the common divisor for the two input numbers.

Points to note

• Out of the two input parameters, if both the two parameters are zero, then the math.gcd() function will give the final output value as zero.
• In the vase where, either of the two parameters is zero, then the math.gcd() function will produce a positive, non zero value as the highest common divisor of the two numbers.
• In the other alternate case where either one of the parameters is a decimal number, then in that case, the math.gcd() function will return a most commonly encountered error called the ‘type error’.
• In the worst case where either one of the parameters given in the math.gcd() function is not a integer number, then in that case the method again returns a ‘type error’.

Sample Program

import math
print (“The final result is :”)
print (math.gcd (100,50))

Sample Output

The final result is : 10

Related Blogs

1. Brief Overview of Python Language
2. Python Career opportunities
3. Python Break Continue
4. Python Control Flow
5. Python Data Types
6. Python Dictionary
7. Python Exception Handling
8.  Python File
9. Python Functions
10. Python Substring