The greatest common divisor of two numbers n and m, written gcd(m,n), is the largest number k such that k is a divisor of both m and n. For example,
One way to find the greatest common divisor of m and n is to try each possible number, starting at the smaller of m and n and counting down until a divisor of both is found. That turns out to be extremely slow when m and n are large.
Another approach is to find the prime factorization of m and n, and to multiply together the common factors. That also turns out to be extremely slow for large numbers.
The Greek mathematician Euclid discovered a simple and efficient way to find the greatest common divisor of two numbers. It is based on the following facts.
(1) gcd(0,n) = n (2) gcd(m,n) = gcd(n mod m, m) (when m > 0)where n mod m is the remainder when you divide n by m. (It is written n % m in C++.) An algorithm starts with two variables i and j set to m and n, respectively. At each stage, it replaces i and j by j mod i and i, respectively, using the fact
gcd(i,j) = gcd(j mod i, i) (when i > 0)That way, gcd(i,j) is always the same. Here is a sample run for m = 10 and n = 36.
i j _____ _____ 10 36 6 10 4 6 2 4 0 2Notice that gcd(10,36) = gcd(6,10) = gcd(4,6) = gcd(2,4) = gcd(0,2) = 2. So, as i and j change, gcd(i,j) is always the same as gcd(m,n), even though m and n do not change. The loop stops when i = 0, with the answer being j.
Question: We tried Euclid's algorithm for m = 10 and n = 36. Does Euclid's algorithm work for the case of m = 36 and n = 10? Try it. What is 10 mod 36?
Make your program print the values of i and j each time around the loop, in a form similar to that shown in the description, so that you can see whether it is performing the algorithm correctly. The printing of i and j is for debugging. Test your program. Do not just presume that it works.
Print this version. Then make a copy of your program, and remove the debugging prints so that the program only shows the greatest common divisor of the two numbers. Also print the second version.
Turn in both printouts. Please put both your name and the assignment number at the top of both versions, as comments. Write "Assignment 2, part 1" on the first part and "Assignment 2, part 2" on the second.