Write a C++ program that implements Euclid's algorithm described in section zyBooks section 10.5 to find the greatest common divisor. Prompt the user for necessary input and compute the correct output. Programs must meet all specifications given, both in the assignment and in the rubric below. No credit will be given for programs that do not compile or run. Please be careful as it is not a good idea to get too far behind and the work will build up and you will likely have a difficult time succeeding in the class. Grading is based on the following criteria: functionality, error-proofing/exception handling, efficient use of course concepts, documentation, and readability in addition to test case results. All programming exercises must include your name at the top of all programs submitted, or you will not receive credit. Note: The question has previously arisen whether you were allowed to use the algorithm and vector header files in your solutions. I think it shows more understanding for our purposes in this class if you do not use the algorithm header (since we are trying to study the details of algorithms). I think it's fine to use vector as long as the algorithm does not specify arrays. If it does specify an array (explicitly or implicitly), you should stick with an array. Let me know if you have any questions./n 10.5 Greatest common divisor and Euclid's algorithm We have already seen how to compute the greatest common divisor of two numbers if the prime factorizations for the two numbers are already known. Unfortunately, computing the prime factorization for an integer is believed to be a hard problem. Cryptographic protocols require computing the gcd of two numbers with hundreds of digits and there is no known way to compute the prime factorization of such large numbers in a reasonable amount of time. There is, however, an efficient way to compute the gcd of two numbers without finding their prime factorizations. The algorithm presented here is in wide use today and is attributed to the Greek mathematician Euclid who lived around 300 B.C. The basis of the algorithm is the following theorem: Theorem 10.5.1: GCD Theorem. Let x and y be two positive integers. Then gcd(x, y) = gcd(y mod x, x). Feedback? Proof 10.5.1: GCD Theorem. Proof. We will prove that a number k is a factor of both x and y if and only if it is a factor of both x and (y mod x). Then the largest common divisor of x and y is also the largest common divisor of x and (y mod x). Suppose that k is a factor of x and y. Then k is also a factor of any linear combination of x and y. If r = y mod x, then y = r+jx for some integer j. Therefore r yjx which means that r is a linear combination of x and y and k divides r. = - Now suppose that k divides x and (y mod x). Again r expressed as a linear combination of x and r: = (y mod x) can be expressed as y - jx for some integer j. y can then be r+ jx = (y − jx) + jx = y Therefore, k also divides y. ■ Feedback? Suppose that x and y are positive integers. According to the GCD theorem, y can be replaced with (y mod x) in the computation of gcd(x, y) and the result will be the same. If it is also true that x < y, then (y mod x) is a smaller number than both x and y, computing the gcd with (y mod x) instead of y is an easier problem. Repeatedly taking the mod function continually decreases the values of the two input numbers. Eventually, the algorithm is left with two numbers, x and y, where one of the two numbers is equal to 0. If x is positive, then gcd(x, 0) = x. The animation below illustrates Euclid's algorithm with two specific numbers. Then the algorithm is stated formally below. PARTICIPATION ACTIVITY 10.5.1: Sample execution of Euclid's algorithm. Start 2x speed gcd (675, 210) 15 = y 675 210 45 30 15 85 r 0 Finished! Captions ^ 1. Euclid's algorithm computes gcd (675, 210) by starting with y = 675 and x = 210, and computing r = y mod x. 2. r = y mod x = 675 mod 210 = 45. 3. The variables are reassigned so that y 210, x = 45, and r = 210 mod 45 = 30. 4. In the next iteration y = 45, x = 30, and r = 45 mod 30 r = 30 mod 15 = 0. = = 15. In the last iteration, y = 30, x = 15, and 5. Since r = 0, the algorithm is finished. gcd (675, 210) is the current value of x, which is 15. Feedback? The extended Euclidean algorithm The gcd of x and y can be expressed as a linear combination of x and y: Theorem 10.5.2: Expressing gcd(x, y) as a linear combination of x and y.. Let x and y be integers, then there are integers s and t such that gcd(x, y) = sx + ty Feedback? = - Instead of proving the theorem above, we illustrate how Euclid's algorithm can be used to find s and t that satisfy the equation. The key fact is that in each iteration of the loop, r is assigned the value (y mod x). Let d = y div x. According to the definition of the mod and div functions, y dx +r, where r is an integer in the range from 0 to 1. The equality can be rearranged to express r as a linear dxr, x combination of x and y: r = y — dx. Thus, each iteration of the loop gives an equation expressing the current value of r as a linear combination of the current x and y. In the last iteration of the loop r = 0 and in the second to last iteration of the loop r is the gcd of the two input integers. The values for s and t in the theorem above can be found by a series of substitutions using the equation from each iteration. The algorithm used to find the coefficients, s and t, such that gcd (x, y) = sx + ty, is called the Extended Euclidean Algorithm. - Note that the gcd is the value computed for r in the second to last iteration of the algorithm. In the last iteration of the algorithm, r = 0. Figure 10.5.1: Euclid's algorithm for finding the greatest common divisor. Input: Two positive integers, x and y. Output: gcd(x, y). If (y < x) Swap x and y. r: = y mod x. While (0) y: = x x:= r. r: = y mod x. End-while Return(x) Feedback?