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

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:-

### 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

## 0 comments:

## Post a Comment

Note: only a member of this blog may post a comment.