First described in the classic geometry book Elements, by the ancient Greek mathematician Euclid (ca. 300 BC, at the book VII, proposition 2), the method of finding de greatest common divisor between the positive numbers and , being consists on the knowledge that the common divisors of and are the same of and . Therefore, we can find this greatest common divisor by replacing the largest number () by the different between the two numbers (), repeatedly, until the two numbers are equal. In TypeScript, we can do that like this:
This method can be very slow if the difference between and is too large. Thankfully, there's another method to find the greatest common divisor between two numbers, that can be described as follows:
- In order to find the greatest common divisor between and , being , perform the division between the two numbers. This operation will give a quotient and a remainder (that we will call and , respectively). Thus, can be described as ;
- If is equal to 0, we stop, because we found that the greatest common divisor of and is . Otherwise, we go back to step 1, making the new and will be the new .
Now, we can start with the implementation of the algorithm above:
The implementation is very straightforward and can be read exactly as is described in steps 1 and 2. We can make the function simpler, by checking, directly, if is equal to zero and only doing the remainder operation afterwards. Therefore, if the function receive a that is equal to zero, we will know that is the greatest common divisor:
This variant is called Euclidean algorithm (in contrast of the first one, which is the Euclid's algorithm) and it significantly faster than the first implementation.
We can also take a different approach. Instead of calling our
gcd function recursively, we can implement our function using a
while loop (analogous to our first implementation above):
And this is another way (analogous to our second implementation above):
Finding the greatest common between three or more numbers
The greatest of three or more numbers is equal the product of the prime factors common to all the numbers (we will explore more of that in a future article), but, you can also calculate the greatest common divisor between pairs of this list of numbers with the same functions we have showed already. So, let's refactor our
gcd function to receive multiple parameters:
Validating our input
Let's guarantee that our functions should always receive, at least, two numbers and that all numbers must not be negative: