Naive methods for calculating gcd

1. Using recursion :

# 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 

2. 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 = = 0  ) 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 

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

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:

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

 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.