This algorithm finds Greatest Common Divisor (GCD) by performing repeated divisi
ID: 3680889 • Letter: T
Question
This algorithm finds Greatest Common Divisor (GCD) by performing repeated division starting from the two numbers we want to find the GCD of until we get a remainder of 0. For example, below are the steps to find the GCD of 60 and 24 using Euclid's algorithm. Divide the larger number by the smaller one. In this case we divide 60 by 24 to get a quotient of 2 and remainder of 12. Next, we divide the smaller number (i.e. 24) by the remainder from the last division (i.e. 12). So we divide 24 by 12. We get a quotient of 2 and remainder of 0. Since we already got a remainder of zero, the last number that we used to divide is the GCD of 24 and 60. In this case 12. Let's look at the steps, find GCD of 24 and 60. 60 ÷ 24 = 2 with a remainder of 12 24 ÷ 12 = 2 with a remainder of 0 We stop here since already got a remainder of 0. The last number we used to divide is 12, so the GCD of 24 and 60 is 12 [2] Description: The program will take two integer numbers as input from the user in an attempt to find the GCD. You should write a program that will take the appropriate input from the user and find out the GCDaccordingly. Youmayassumetheuserinputnumbersarevalid. in python
Explanation / Answer
def gcd(a, b):
"""Returns the greatest common divisor of a and b.
Should be implemented using recursion.
>>> gcd(34, 19)
1
>>> gcd(39, 91)
13
>>> gcd(20, 30)
10
>>> gcd(40, 40)
40
"""
if b > a:
return gcd(b, a)
if a % b == 0:
return b
return gcd(b, a % b)
# take input from the user
num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))
print("The GCD of", num1,"and", num2,"is", gcd(num1, num2))
/*
Input:
Enter first number: 12
Enter second number: 24
('The GCD of', 12, 'and', 24, 'is', 12)
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.