Solution: GCD of Two Integers Using the <requires> Clause

Solution

The most famous solution to the GCD problem is Euclid’s algorithm. Euclid’s algorithm is an efficient algorithm that computes the GCD of two given integers. . On line 6, we create a concept Number and on line 9 it is required by the function for both the template parameters. Because the same concept is required for both template parameters, only integer numbers can be passed to the function.

The function gcd() is based on the following observation: if d divides a and d divides b, d divides a - b as well. The GCD of a and b is the same as the GCD of a - b and b.

• Stop if a == b. The GCD of a and b, of course, is a. If not, go to the next step.
• If a > b, replace a with a-b, then go to the first step.
• If b > a, replace b with b-a, then go to the first step.