CPSC250A Assignment 1 - Euclid's Algorithm for GCD

Due Monday September 12

In assignment 0 you wrote a program that computed the GCD using brute force. It is possible to compute the GCD more quickly using Euclid's algorithm.


The recursive definition of Euclid's algorithm is:

gcd(a, b) = gcd(b, a % b) (where a >= b)
gcd(a, 0) = a

The file gcd.cc contains the outline for a program that reads in a pair of integers from the user, passes the entered integers to the undefined method GCD, and prints the result. The GCD method should use Euclid's algorithm to find the greatest common divisor of the two specified integers. The algorithm can be programmed using either recursion or a loop. The method can assume that the two parameters are positive integers, but should have a method comment that specifies this assumption. Be sure to test your code on multiple examples and on the cs server.


Tar your code in a file that contains your name and submit it on the course Inquire site.