Calculating HCF or GCD Using Euclid Algorithm In Python

In this article, you’ll learn how to calculating HCF or GCD using euclid algorithm in Python. Before we get started, if you want to conditional statements in python, please go through the following article: Define Functions 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.

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 is 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.

We can verify this algorithm by taking the same two numbers 12 & 8, having a common divisor d = 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

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:

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

Calculating GCD Using Euclid Algorithm In Python

The article was published on October 1, 2020 @ 8:34 AM