Challenge: Euclidean Algorithm

Euclidean Algorithm

The Euclidean algorithm is a technique used to compute the greatest common divisor (GCD) of two numbers, i.e. the largest number that divides both of them without leaving a remainder.

The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger value of the two is replaced by the difference between both numbers. Keep this logic in mind while solving the following challenge.

Problem Statement:

Given two integers a and b, calculate the largest number that divides both of them without leaving a remainder (a.k.a. GCD).

Inputs

Two integers a and b. For instance, a = 1071, b = 462.

Output

An integer which will be a and b's GCD. For a = 1071 and b = 462, the output will be 21.

Coding Challenge

Take a close look and design a step-by-step algorithm before jumping on to the implementation. This problem is designed for your practice, so try to solve it on your own first. If you get stuck, you can always refer to the hint and solution provided in the code tab. Good Luck!