Write a program to compute the greatest common divisor ( GCD ) of two given inte
ID: 3536571 • Letter: W
Question
Write a program to compute the greatest common divisor (GCD) of two given integers, using the Euclidean Algorithm. You are encouraged to implement both the recursive and non-recursive versions. The input consists of several lines, with each line containing two positive integers, a and b, separated by a white space (a; b < 10000). A pair of 0 0 terminates the input. The output should have one GCD per line for each pair in the input. Please download the sample input and sample output files provided and test with your program according to the instructions.<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />
Important:
Your program should prompt the user for input, and it should accept only valid input. Your output should be organized as follows:
10 15 5
55 14 1
2 1024 2
0 0
Explanation / Answer
"" if you have any problem with this code please discuss with me before rating"""
""" iterative version """
def GCD(a,b):
while b!=0:
t = b
b = a%t
a = t
return a;
while 1:
a=int(raw_input("Enter first integer: "));
b=int(raw_input("Enter second integer: "));
if a==0 and b==0:
break;
else:
print "result: ",GCD(a,b);
""" recursive version """
def GCD(a,b):
if b==0:
return a
else:
return GCD(b, a%b);
while 1:
a=int(raw_input("Enter first integer: "));
b=int(raw_input("Enter second integer: "));
if a==0 and b==0:
break;
else:
print "result: ",GCD(a,b);
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.