(Compute the greatest common divisor) For Listing 5.8, another solution to find the greatest common divisor of two integers n1 and n2 is as follows: First find d to be the minimum of n1 and n2, and then check whether d, d - 1, d - 2, ..., 2, or
1 is a divisor for both n1 and n2 in this order. The first such common divisor is the greatest common divisor for n1 and n2.
Compute the greatest common divisor Program code:
# Function to find the greatest common divisor (GCD) of two integers
def gcd(n1, n2):
# Find the minimum of n1 and n2
d = min(n1, n2)
# Check each number from d to 1 as a potential common divisor
while d >= 1:
# Check if d is a divisor for both n1 and n2
if n1 % d == 0 and n2 % d == 0:
# d is the greatest common divisor, so we can return it
return d
d -= 1 # Decrement d by 1 to check the next potential divisor
# If no common divisor is found, return 1 as the default GCD
return 1
# Initialize the variables
n1 = 84
n2 = 18
#Call the method gcd and output stored in result variable
result = gcd(n1, n2)
#Display output
print("The greatest common divisor of", n1, "and", n2, "is:", result)
Executed Output:
The greatest common divisor of 84 and 18 is: 6