# Support Our Site

To ensure we can continue delivering content and maintaining a free platform for all users, we kindly request that you disable your adblocker. Your contribution greatly supports our site's growth and development.

# Calculating GCD Using Euclid Algorithm In Python

For any two positive integer number m and n, GCD ( greatest common divisor) is the largest integer number which divides them evenly.

So for the following two numbers 8 and 12,  4 is the largest number which divides them evenly hence 4 is the GCD of 8 & 12. Since 1 is the divisor of every number, so there is always at least one common divisor for a pair of numbers.

In order to calculate GCD for a pair number m & n programmatically. Typically one would go through all the factors of m and n respectively and store them in a list then extract the common factors in both the list and find out the largest factor. This will work although this isn't the most efficient way of calculating GCD, for two really large numbers.

## Euclid algorithm

Euclid, a Greek mathematician in 300 B.C. discovered an extremely efficient way of calculating GCD for a given pair of numbers. Euclid observed that for a pair of numbers m & n assuming  `m>n` and n is not a divisor of m.

Number m can be written as `m = qn + r`, where q in the quotient and r is the reminder. Recursive substitution of r with q and q with m until the remainder is 0 will ultimately deliver the GCD for the pair since `gcd(n,0) = n`.

Mathematically i.e.

``gcd(m, n) == gcd(n, m % n)``

We can verify this algorithm by taking the same two numbers 12 & 8, having a common divisor d = 4

``````# m = qn + r
12 = q * 8 + r
# q = 1 & n = 8 & r =4
12 = 8 + 4
#Substituiting m with n and q with r
#q =2 & n = 4  &   r =
08 = 4*2 + 0
#Substituiting m with n and q with r
GCD = 4 ``````

Euclid algorithm remarkably increases the efficiency of the program calculating GCD as the reminder keeps on decreasing resulting in saving the precious computer cycles.

## Program to find GCD In Python

``````def gcd(m,n):
if m< n:
(m,n) = (n,m)
if(m%n) == 0:
return n
else:
return (gcd(n, m % n)) # recursion taking place

# calling function with parameters and printing it out
print(gcd(8,12))``````

This is a simple recursive function, which will return the greatest common divisor when the condition is met, we just need to pass the numbers as parameters in the function call.

The same function can also be made on the top of a while loop with the controlling statement being (m%n != 0) as follows:

``````def gcd(m,n):
if m< n:
(m,n) = (n,m)
while (m % n != 0):
(m, n) = (n, m % n)
return n

# calling function with parameters and printing it out
print(gcd(8,12))``````

Both recursive functions return the GCD for a given pair of numbers efficiently even if the numbers are huge.

PYTHON

# Latest Articles

Latest from djangocentral

## How to Use Subquery() in Django With Practical Examples

In the realm of web development, Django stands as a powerful and versatile framework for building robust applications. One of the key aspects of developing efficient and optimized web applications is handling database queries effectively. In this article…

## DRF Serializer: Handling OrderedDict and Converting It to a Dictionary or JSON

In Django Rest Framework (DRF) tests, when you access serializer.data, you might encounter an OrderedDict instead of a regular dictionary. This behavior is intentional and reflects the design of DRF's serialization process.Understanding the Problem The u…

## Django Rest Framework CheetSheet: Mastering API Development

Django Rest Framework (DRF) is a powerful toolkit that makes building robust and scalable web APIs with Django a breeze. Whether you're a seasoned Django developer or a newcomer, having a comprehensive cheat sheet at your disposal can be a game-changer. …