How does gcd work in python?

View Discussion

Improve Article

Save Article

View Discussion

Improve Article

Save Article

The Highest Common Factor [HCF], also called gcd, can be computed in python using a single function offered by math module and hence can make tasks easier in many situations.

Naive Methods to compute gcd

Way 1: Using Recursion

Python3

def hcfnaive[a, b]:

    if[b == 0]:

        return abs[a]

    else:

        return hcfnaive[b, a % b]

a = 60

b = 48

print["The gcd of 60 and 48 is : ", end=""]

print[hcfnaive[60, 48]]

Output

The gcd of 60 and 48 is : 12

Way 2: Using Loops 

Python3

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 = 60

b = 48

print ["The gcd of 60 and 48 is : ", end=""]

print [computeGCD[60,48]]

Output

The gcd of 60 and 48 is : 12

Way 3: Using Euclidean Algorithm 

Python3

def computeGCD[x, y]:

   while[y]:

       x, y = y, x % y

    return abs[x]

a = 60

b = 48

print ["The gcd of 60 and 48 is : ",end=""]

print [computeGCD[60, 48]]

Output:

The gcd of 60 and 48 is : 12

• Both numbers are 0, gcd is 0
• If only either number is Not a number, Type Error is raised.

View Discussion

Improve Article

Save Article

View Discussion

Improve Article

Save Article

Given two numbers. The task is to find the GCD of the two numbers.

Using STL :

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]

Parameter:

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.

Python3

import math

print["The gcd of 60 and 48 is : ", end=""]

print[math.gcd[60, 48]]

Output

The gcd of 60 and 48 is : 12

Using Recursion :

Python3

def hcf[a, b]:

    if[b == 0]:

        return a

    else:

        return hcf[b, a % b]

a = 60

b = 48

print["The gcd of 60 and 48 is : ", end=""]

print[hcf[60, 48]]

Output

The gcd of 60 and 48 is : 12

Using Euclidean Algorithm :

The Euclid’s algorithm [or Euclidean Algorithm] is a method for efficiently finding the greatest common divisor [GCD] of two numbers. The GCD of two integers X and Y is the largest number that divides both of X and Y [without leaving a remainder].

Pseudo Code of the Algorithm-

1. Let  a, b  be the two numbers
2. a mod b = R
3. Let  a = b  and  b = R
4. Repeat Steps 2 and 3 until  a mod b  is greater than 0
5. GCD = b
6.  Finish

Python3

def gcd[a, b]:

    if [a == 0]:

        return b

    if [b == 0]:

        return a

    if [a == b]:

        return a

    if [a > b]:

        return gcd[a-b, b]

    return gcd[a, b-a]

a = 98

b = 56

if[gcd[a, b]]:

    print['GCD of', a, 'and', b, 'is', gcd[a, b]]

else:

    print['not found']

Output

GCD of 98 and 56 is 14