Code for Greatest Common Divisor in Python

Question

The greatest common divisor  GCD  of a and b is the largest number that divides both of them with no remainder   One way to find the GCD of two numbers is Euclid   s algorithm  which is based on the observation that if r is the remainder when a is divided by b  then gcd a  b    gcd b  r   As a base case  we can use gcd a  0    a   Write a function called gcd that takes parameters a and b and returns their greatest common divisor

User · Answer

I had to do something like this for a homework assignment using while loops  Not the most efficient way  but if you don t want to use a function this works   num1   20 num1 list      num2   40 num2 list      x   1 y   1 while x  lt   num1      if num1   x    0          num1 list append x      x    1 while y  lt   num2      if num2   y    0          num2 list append y      y    1 xy   list set num1 list  intersection num2 list   print xy -1

User · Answer

def gcd m n       return gcd abs m-n   min m  n   if  m-n  else n

User · Answer

def gcd a b       if b  gt  a          return gcd b a      r   a b     if r    0          return b     return gcd r b

User · Answer

using recursion   def gcd a b       return a if not b else gcd b  a b    using while   def gcd a b     while b      a b   b  a b   return a   using lambda   gcd   lambda a b   a if not b else gcd b  a b    gt  gt  gt  gcd 10 20   gt  gt  gt  10

User · Answer

a int raw input  1st no  n    b int raw input  2nd no  n     def gcd m n       z abs m-n      if  m-n   0          return n     else          return gcd z min m n     print gcd a b    A different approach based on euclid s algorithm

User · Answer

def  grateest common devisor euclid p  q       if q  0           return p     else          reminder   p q         return  grateest common devisor euclid q  reminder   print  grateest common devisor euclid 8 3

User · Answer

This program will find the hcf of a given list of numbers   A    65  20  100  85  125       creates and initializes the list of numbers  def greatest common divisor  A     iterator   1   factor   1   a length   len  A    smallest   99999   get the smallest number for number in  A   iterate through array   if number  lt  smallest   if current not the smallest number     smallest   number  set to highest  while iterator  lt   smallest   iterate from 1     smallest number for index in range 0  a length    loop through array   if  A index    iterator    0   if the element is not equally divisible by 0     break  stop and go to next element   if index     a length - 1    if we reach the last element of array     factor   iterator  it means that all of them are divisibe by 0 iterator    1  let s increment to check if array divisible by next iterator  print the factor print factor  print  The highest common factor of     for element in A    print element  print   is       greatest common devisor A

User · Answer

The value swapping didn t work well for me  So I just set up a mirror-like situation for numbers that are entered in either a  lt  b OR a   b    def gcd a  b       if a  gt  b          r   a   b         if r    0              return b         else              return gcd b  r      if a  lt  b          r   b   a         if r    0              return a         else              return gcd a  r   print gcd 18  2

User · Answer

gcd   lambda m n  m if not n else gcd n m n

User · Answer

This version of code utilizes Euclid s Algorithm for finding GCD   def gcd recursive a  b       if b    0          return a     else          return gcd recursive b  a   b

User · Answer

The algorithms with m-n can runs awfully long   This one performs much better   def gcd x  y       while y    0           x  y     y  x   y      return x

User · Answer

Very concise solution using recursion   def gcd a  b       if b    0          return a     return gcd b  a b

User · Answer

It s in the standard library    gt  gt  gt  from fractions import gcd  gt  gt  gt  gcd 20 8  4   Source code from the inspect module in Python 2 7    gt  gt  gt  print inspect getsource gcd  def gcd a  b          Calculate the Greatest Common Divisor of a and b       Unless b  0  the result will have the same sign as b  so that when     b is divided by it  the result comes out positive               while b          a  b   b  a b     return a   As of Python 3 5  gcd is in the math module  the one in fractions is deprecated  Moreover  inspect getsource no longer returns explanatory source code for either method

User · Answer

For a gt b  def gcd a  b        if a lt b           a b b a              while b  0           r b b a r         a r     return a   For either a gt b or a lt b  def gcd a  b        t   min a  b         Keep looping until t divides both a  amp  b evenly     while a   t    0 or b   t    0          t -  1      return t

User · Answer

def gcdIter a  b   gcd  min  a b  for i in range 0 min a b        if  a gcd  0 and b gcd  0           return gcd         break     gcd- 1

User · Answer

I think another way is to use recursion  Here is my code   def gcd a  b       if a  gt  b          c   a - b         gcd b  c      elif a  lt  b          c   b - a         gcd a  c      else          return a

User · Answer

def gcdRecur a  b               a  b  positive integers      returns  a positive integer  the greatest common divisor of a  amp  b                Base case is when b   0     if b    0          return a        Recursive case     return gcdRecur b  a   b

User · Answer

This code calculates the gcd of more than two numbers depending on the choice given by    the user  here user gives the number  numbers       count   input   HOW MANY NUMBERS YOU WANT TO CALCULATE GCD  n   for i in range 0  count     number   input  ENTER THE NUMBER    n     numbers append number  numbers sorted   sorted numbers  print   NUMBERS SORTED IN INCREASING ORDER n  numbers sorted gcd   numbers sorted 0   for i in range 1  count     divisor   gcd   dividend   numbers sorted i    remainder   dividend   divisor   if remainder    0     gcd   divisor   else       while not remainder    0         dividend one   divisor       divisor one   remainder       remainder   dividend one   divisor one       gcd   divisor one  print  GCD OF    count  NUMBERS IS  n   gcd

User · Answer

Here s the solution implementing the concept of Iteration   def gcdIter a  b               a  b  positive integers      returns  a positive integer  the greatest common divisor of a  amp  b              if a  gt  b          result   b     result   a      if result    1          return 1      while result  gt  0          if a   result    0 and b   result    0              return result         result -  1

User · Answer

in python with recursion   def gcd a  b       if a b    0          return b     return gcd b  a b

[python] Code for Greatest Common Divisor in Python

Examples related to python