# Python: Compute the 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.

**What is the difficulty level of this exercise?**

Test your Python skills with w3resource's quiz

## Python: Tips of the Day

**Try-catch-else construct:**

try: foo() except Exception: print("Exception occured") else: print("Exception didnt occur") finally: print("Always gets here")

**New Content published on w3resource:**- Scala Programming Exercises, Practice, Solution
- Python Itertools exercises
- Python Numpy exercises
- Python GeoPy Package exercises
- Python Pandas exercises
- Python nltk exercises
- Python BeautifulSoup exercises
- Form Template
- Composer - PHP Package Manager
- PHPUnit - PHP Testing
- Laravel - PHP Framework
- Angular - JavaScript Framework
- Vue - JavaScript Framework
- Jest - JavaScript Testing Framework