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
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
You May Also Like,
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.
Using 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
You May Also Love,
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
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.