gcd () in Python



Naive methods for calculating gcd

  1. Using recursion :
  2. # Python code to demonstrate naive
    # method for calculating gcd (recursion)

     

    def hcfnaive (a, b):

    if (b = = 0 ):

    return a

    else :

    return hcfnaive (b, a % b)

      

    a = 60

    b = 48

      
    # prints 12

    print ( "The gcd of 60 and 48 is:" , end = "")

    print (hcfnaive ( 60 , 48 ))

    Output:

     The gcd of 60 and 48 is: 12 

  3. Using

    # Python code to demonstrate naive
    # method for calculating gcd (Loops)

     

     

    def computeGCD (x, y):

     

    if x & gt; y:

    small = y

    else :

    small = x

      for i in range ( 1 , small + 1 ):

      if ((x % i = = ) and (y % i = = 0 )):

    gcd = i

      

    return gcd

     

    a = 60

    b = 48

     
    # prints 12

    print ( " The gcd of 60 and 48 is: " , end = " ")

    print (computeGCD ( 60 , 48 ))

    Output:

     The gcd of 60 and 48 is: 12  
  4. Using the

    # Python code to demonstrate naive
    # method for calculating gcd (euclidean algo)

     

     

    def computeGCD (x, y):

     

    while (y):

    x , y = y, x % y

     

    return x

     

    a = 60

    b = 48

      
    # prints 12

    print ( "The gcd of 60 and 48 is:" , end = " ")

    print (computeGCD ( 60 , 48 ))

    Output:

     The gcd of 60 and 48 is: 12 
  5. Using the Python math.gcd () function

    Using gcd () can evaluate the same gcd in just one line.

      math.gcd (x, y)   Parameters:  x: Non-negative integer whose gcd has to be computed. y: Non-negative integer whose gcd has to be computed.  Return Value:  This method will return 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. 

    # Python code for demonstrating gcd ()
    # method for calculating gcd

     

    import math

     
    # prints 12

    print ( "The gcd of 60 and 48 is:" , end = "")

    print (math.gcd ( 60 , 48 ))

    Output:

     The gcd of 60 and 48 is: 12 

     

    Common exceptions

    Some common exceptions in this function:

  • Both numbers are 0, gcd is 0
  • If only one number is not a number, a type error occurs.

# Python code to demonstrate gcd ()
# method exceptions

 

import math

 
# prints 0

print ( "The gcd of 0 and 0 is: " , end = " ")

print (math.gcd ( 0 , 0 ))

  
# Throws an error

print ( " The gcd of a and 13 is: " , end = "")

print ( math.gcd ( `a` , 13 ))

Output:

 The gcd of 0 and 0 is: 0 The gcd of a and 13 is: 

Runtime error:

 Traceback (most recent call last) : File "/home/94493cdfb3c8509146254862d12bcc97.py", line 12, in print (math.gcd (`a`, 13)) TypeError:` str` object cannot be interpreted as an integer 

This article is provided by Manjeet Singh . If you are as Python.Engineering and would like to contribute, you can also write an article using contribute.python.engineering or by posting an article contribute @ python.engineering. See my article appearing on the Python.Engineering homepage and help other geeks.

Please post comments if you find anything wrong or if you`d like to share more information on the topic discussed above.