How to Find the Greatest Common Divisor in Python

In this example we will show how to calculate the greatest common divisor(GCD) in Python.

2. Method

In order to get the greatest common divisor of x and y, we need to use the for loop for variable d from 1 to the minimum of x and y, and checking the remainders of x and y dividing d. If the remainders are zero, d will be recorded as the common divisor of x and y. When the loop ends, we can get the maximum of all recorded d, i.e. the greatest common divisor.

Source Code

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# Define the function to find the greatest common divisor
def hcf(x, y):

    # Get the minimum of two numbers
    if x > y:
        smaller = y
    else:
        smaller = x

    # Using a for loop to checking the remainder
    for i in range(1, smaller + 1):
        if ((x % i == 0) and (y % i == 0)):
        # If all are zero, then assign
            hcf = i
    return hcf

# Enter two numbers
num1 = int(input("Enter the first number: "))
num2 = int(input("Enter the second number: "))

print("The greatest common divisor: ", hcf(num1, num2))

Enter the first number: 4
Enter the second number: 8
The greatest common divisor: 4

Enter the first number: 24
Enter the second number: 45
The greatest common divisor: 3