Question

Write an algorithm that finds the greatest common divisor of two integers.

Short answer

The provided steps describe the Euclidean algorithm for computing the greatest common divisor of two integers and discusses a possible implementation. This algorithm functions by iterative division and remainder calculation until the remainder is 0.

Step-by-step solution

Understanding the Euclidian Algorithm

Euclidean Algorithm is a way to find the greatest common divisors (GCDs) of two numbers. In this process, the larger number is to be divided by the smaller one. Then, divide the divisor by the remaining, continuing this process until the remainder is 0; the GCD is the last non-zero remainder.

Implementation of the Algorithm

Start by checking if the second number is 0. If it is, return the first number because the GCD of a number and 0 is the number itself. If the second number is not 0, recursively call the function, swapping the positions of the numbers and replacing the first number with the modulus of the two numbers.

Base Case

The algorithm stops when there is no remainder left - that is when the second number becomes 0, which is the base case of our recursive implementation. You return the first number in this case because the GCD of a number and 0 is the number itself.