GCD Python: 6 Best Ways to Compute HCF or GCD in Python

GCD Python: In this article, we have discussed different ways of computing GCD of two numbers in Python.

Note that GCD stands for Greatest Common Divisor.

GCD also called as HCF(Highest Common Factor).

We can calculate GCD by using Recursion Function, Loops, Euclidean algorithm, Math, Fractions and Numpy libraries.

What is GCD?

GCD is nothing but Greatest Common Divisor or Highest Common Factor of input numbers.

The Largest Integer will divide and return the difference.

For example, The GCD of 14 and 16 is 2.

Different Ways to Compute GCD

GCD can be computed by following ways.

Using Recursion Function
Leveraging Loops
Using Euclidean Algorithm
With math.gcd() Function

Using Recursion Function

Recursion is nothing but a mechanism in which a function calls itself.

Using recursion program, solution to the bigger problem is mentioned in terms of smaller problems.

Lets go through the implementation below.

def recursiveGCD(a,b): 
    if(b==0): 
        return a 
    else: 
        return recursiveGCD(b,a%b)  
a=54
b=72
  
print("The GCD is", recursiveGCD(a, b))

Output:
The GCD is 18

Leveraging Loops

Lets compute GCD by leveraging the loop.

def loopGCD(a, b): 
  
    if a > b: 
        tiny = b 
    else: 
        tiny = a 
    for j in range(1, tiny+1): 
        if((a % j == 0) and (b % j == 0)): 
            finalgcd = j 
              
    return finalgcd 
  
a=54
b=72

print("The GCD is", loopGCD(a, b))

Output:
The GCD is 18

Using Euclidean Algorithm

Mathematically Euclidean Algorithm is an impressive way for computing the greatest common divisor (GCD) of two numbers (integers), where the largest number that divides both without having a remainder.

This Algorithm is named after the ancient Greek mathematician Euclid.

sing Euclidean Algorithm, we can compute GCD by leveraging as below.

def algoGCD(a, b): 
  
   while(b): 
       a, b = b, a % b 
  
   return a 

a=54
b=72

print("The GCD is", algoGCD(a, b))

Output:
The GCD is 18

With math.gcd() Function

The math package provides gcd() method , which will compute the gcd of given numbers.

Its just a one line code.

import math 
  
a=54
b=72

print("The GCD is", math.gcd(a, b))

Output:
The GCD is 18

Using fractions.gcd() Function

The fractions package provides gcd() method, this will calculate the gcd with one line of code.

import fractions
  
a=54
b=72
  
print("The GCD is", fractions.gcd(a, b))

Output:
The GCD is 18

Using numpy.gcd() Function

The numpy package provides gcd() method, using this we can compute the gcd with one line of code.

Note that gcd() method is added into numpy library from version 1.15.

So if your using any version older than 1.15, then gcd function will not be available.

import numpy

a=54
b=72

print("The Value is", numpy.gcd(a,b))

Output:
The GCD is 18

Conclusion

Above are the some of the best methods to compute GCD in Python.

To conclude this tutorial, we covered various methods with examples to calculate HCF of two numbers using Python progamming language.

5/5 - (2 votes)

6 Best Ways to Compute HCF or GCD in Python