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

Python Basic: Exercise-31 with Solution

GCD Calculator

Write a Python program that computes 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:

# Define a function to calculate the greatest common divisor (GCD) of two numbers.
def gcd(x, y):
    # Initialize gcd to 1.
    gcd = 1
    
    # Check if y is a divisor of x (x is divisible by y).
    if x % y == 0:
        return y
    
    # Iterate from half of y down to 1.
    for k in range(int(y / 2), 0, -1):
        # Check if both x and y are divisible by k.
        if x % k == 0 and y % k == 0:
            # Update the GCD to the current value of k and exit the loop.
            gcd = k
            break
    
    # Return the calculated GCD.
    return gcd

# Print the GCD of specific pairs of numbers.
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

Explanation:

Here is a simple implementation of the Euclidean algorithm for finding the greatest common divisor (GCD) of two integers.

The function "gcd(x,y)" starts by initializing the variable "gcd" to 1, and then checks if "x" is divisible by "y". If it is, it returns "y" as the GCD.

If "x" is not divisible by "y", it enters a "for" loop. In each iteration, it checks if "k" is a common divisor of "x" and "y", and if it is, it assigns the value of k to the variable "gcd" and breaks out of the loop. Finally, the function returns the value of GCD of "x" and "y".

Last three print statements of the said code call the function with different inputs, and print the output as "GCD of 12 & 17 = 1", "GCD of 4 & 6 = 2" and "GCD of 336 & 360 = 24".

Flowchart:

Sample Solution-2:

Python Code:

# Define a function to calculate the greatest common divisor (GCD) of two numbers.
def gcd(x, y):
    # Initialize z as the remainder of x divided by y.
    z = x % y
    
    # Use a while loop to find the GCD.
    while z:
        # Update x to y, y to z, and calculate a new value for z (remainder of x divided by y).
        x = y
        y = z
        z = x % y
    
    # When z becomes 0, y contains the GCD, so return y.
    return y

# Print the GCD of specific pairs of numbers.
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

Explanation:

The said code defines a function "gcd(x, y)" that takes two integers as its argument and will return the greatest common divisor (GCD) of the two numbers. It uses Euclidean algorithm to calculate the GCD.

It starts by initializing the variable "z" to the value of the remainder when x is divided by y.

Then, the function enters a while loop that continues until "z" is 0. Inside the loop, it updates the values of x and y with y and z respectively, and calculates the new value of z as x modulo y.

Finally it returns the value of y, which is the GCD of x and y.

Last three print statements of the said code call the function "gcd(x, y)" with different inputs, and print the output.

Flowchart:

Sample Solution-3:

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

Python Code:

# Import the 'reduce' function from the 'functools' module
# and rename the 'gcd' function from the 'math' module as '_gcd'.
from functools import reduce
from math import gcd as _gcd

# Define a function 'gcd' that calculates the greatest common divisor (GCD) of a list of numbers.
def gcd(nums):
    # Use the 'reduce' function to apply the '_gcd' function cumulatively to the elements in 'nums'.
    # This effectively finds the GCD of all the numbers in the list.
    return reduce(_gcd, nums)

# Define a list 'nums' with pairs of numbers.
nums = [336, 360]
print("GCD of", ','.join(str(e) for e in nums))  # Print a message indicating the GCD calculation.
print(gcd(nums))  # Calculate and print the GCD of the numbers in the 'nums' list.

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

Explanation:

The said code imports the "reduce" function from the "functools" module, and the "gcd" function from the "math" module. Now it defines a new function "gcd(nums)" that takes a list of integers as input and returns the greatest common divisor (GCD) of all the integers in the list using the "reduce" function.

The "reduce" function applies a binary operation (in this case, the "gcd" function) cumulatively to the elements of an iterable (in this case, the list of integers) so as to reduce the iterable to a single value.

Finally it calls the function with different inputs and prints the GCD of the inputs.

It's more efficient than the previous two solutions as it finds GCD of multiple numbers at once and doesn't require calling the GCD function multiple times.

Flowchart:

Python Code Editor:

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.