Python: Greatest common divisor (GCD) of two positive integers

Python Basic: Exercise-31 with Solution

Write a Python program to compute the greatest common divisor (GCD) of two positive integers.

The greatest common divisor (GCD) of two nonzero integers a and b is the greatest positive integer d such that d is a divisor of both a and b; that is, there are integers e and f such that a = de and b = df, and d is the largest such integer. The GCD of a and b is generally denoted gcd(a, b).

Pictorial Presentation:

Sample Solution-1:

Python Code:

def gcd(x, y):
   gcd = 1   
   if x % y == 0:
       return y   
   for k in range(int(y / 2), 0, -1):
       if x % k == 0 and y % k == 0:
           gcd = k
           break 
   return gcd
print("GCD of 12 & 17 =",gcd(12, 17))
print("GCD of 4 & 6 =",gcd(4, 6))
print("GCD of 336 & 360 =",gcd(336, 360))

Sample Output:

GCD of 12 & 17 = 1
GCD of 4 & 6 = 2
GCD of 336 & 360 = 24

Flowchart:

Visualize Python code execution:

The following tool visualize what the computer is doing step-by-step as it executes the said program:

Sample Solution-2:

Python Code:

def gcd(x, y):
 z = x % y
 while z:
   x = y
   y = z
   z = x % y
 return y
print("GCD of 12 & 17 =",gcd(12, 17))
print("GCD of 4 & 6 =",gcd(4, 6))
print("GCD of 336 & 360 =",gcd(336, 360))

Sample Output:

GCD of 12 & 17 = 1
GCD of 4 & 6 = 2
GCD of 336 & 360 = 24

Flowchart:

Visualize Python code execution:

The following tool visualize what the computer is doing step-by-step as it executes the said program:

Sample Solution-3:

Use functools.reduce() and math.gcd() over the given list.

Python Code:

from functools import reduce
from math import gcd as _gcd
def gcd(nums):
  return reduce(_gcd, nums)
nums = [336, 360]
print("GCD of",','.join(str(e) for e in nums))
print(gcd(nums))
nums = [12, 17]
print("GCD of",','.join(str(e) for e in nums))
print(gcd(nums))
nums = [4, 6]
print("GCD of",','.join(str(e) for e in nums))
print(gcd(nums))
nums = [24, 30, 36]
print("GCD of",','.join(str(e) for e in nums))
print(gcd(nums))

Sample Output:

GCD of 336,360
24
GCD of 12,17
1
GCD of 4,6
2
GCD of 24,30,36
6

Flowchart:

Visualize Python code execution:

The following tool visualize what the computer is doing step-by-step as it executes the said program:

Python Code Editor:

Have another way to solve this solution? Contribute your code (and comments) through Disqus.

Previous: Write a Python program that will accept the base and height of a triangle and compute the area.
Next: Write a Python program to get the least common multiple (LCM) of two positive integers.