GCD Program in Python | Different ways to implement GCD Program in Python

GCD is the abbreviation for Greatest Common Divisor which is a mathematical equation to find the largest number that can divide both the numbers given by the user. Sometimes this equation is also referred as the greatest common factor.

For example, the greatest common factor for the numbers 20 and 15 is 5, since both these numbers can be divided by 5. This concept can easily be extended to a set of more than 2 numbers as well, where the GCD will be the number which divides all the numbers given by the user.

Image source

Applications of GCD

GCD has a wise number of applications in 

•  Number theory
•  Encryption technologies like RSA
•  Modular arithmetic 
•  Simplifying fractions that are present in an equation

 

 Different ways to implement GCD Program in Python

   There are different ways to implement GCD program in Python. Here I am presenting some most popular and widely used implementations for you.

1. Using standard library functions to find GCD in Python

   In Python, the math module contains a number of mathematical operations, which can be performed with ease using the module. math.gcd() function compute the greatest common divisor of 2 numbers mentioned in its arguments.

    Syntax: math.gcd(x, y)

    In the above syntax the parameters are as follows

•     x : Non-negative integer whose gcd has to be computed.
•     y : Non-negative integer whose gcd has to be computed.
•     Returns: An absolute/positive integer value after calculating the GCD of given parameters x and y.
•     Exceptions: When Both x and y are 0, function returns 0, If any number is a character, Type error is raised.

 The following examples shows how to use math.gcd()

# importing "math" for mathematical operations
import math

# prints 
print("The gcd of 24 and 36 is : ")
print(math.gcd(24, 36))

The following is the out put of the above program

The gcd of 24 and 36 is : 
12

 2. Using iterative process (Loops)

def computeGCD(x, y): 
    if x > y: 
        small = y 
    else: 
        small = x 
    for i in range(1, small+1): 
        if((x % i == 0) and (y % i == 0)): 
            gcd = i     
    return gcd 
a = 6
b= 4
 
print ("The gcd of 6 and 4 is : ",end="") 
print (compute GCD(6,4)) 

Output:-

The gcd of 6 and 4 is : 2

 3. Using Recursion

def GCD(a,b): 
    if(b==0): 
        return a  # base case 
    else: 
        return GCD(b,a%b) # General Case 
a = 60
b= 48
# prints 12 
print ("The gcd of 60 and 48 is :") 
print (GCD(60,48)) 

 Output:-

The gcd of 60 and 48 is :
12