Assignment Due: Friday, November 9, 2012 at 5:00 PM
Problem #2, Homework #2
Write a function gcd(m, n) that calculates the greatest common divisor of m and n. The greatest divisor of m and n is the largest positive integer k that evenly divides m and n (that is, divides both of them giving a remainder of 0). Use Euclid’s algorithm to calculate this. Here is one very succinct way to describe the algorithm (as usual in Python, m % n is the remainder of m when divided by n):
When n is 0, the value m is the greatest common divisor of m and n. Then write a program that calls your function repeatedly, until the user enters 0 for n. Here is an example run of such a program. What the user types is in italics and the symbol “↵” means to type a return or enter. Please do not try to make the input in italics and show the return symbol in your output, of course!
First number (0 to stop): 113↵ Second number: 293↵ The greatest common divisor of 293 and 113 is 1 First number (0 to stop): 14↵ Second number: 18↵ The greatest common divisor of 18 and 14 is 2 First number (0 to stop): -30↵ Second number: -66↵ The greatest common divisor of -66 and -30 is 6 First number (0 to stop): 7↵ Second number: 0↵ The greatest common divisor of 0 and 7 is 7 First number (0 to stop): 0↵
Please call your program “gcd.py”.
ECS 10, Basic Concepts of Computing
Fall Quarter 2012