SHARE
SPREAD
HELP

The Tradition of Sharing

Help your friends and juniors by posting answers to the questions that you know. Also post questions that are not available.


To start with, Sr2Jr’s first step is to reduce the expenses related to education. To achieve this goal Sr2Jr organized the textbook’s question and answers. Sr2Jr is community based and need your support to fill the question and answers. The question and answers posted will be available free of cost to all.

 

#
Authors:
Y Daniel Lang
Chapter:
.loops
Exercise:
Programming Excercises
Question:16 | ISBN:978013274719 | Edition: 6

Question

(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.

TextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbook

Answer

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

 

0 0

Discussions

Post the discussion to improve the above solution.