## Objective

Create a function to find the greatest common divisor of two integers.

## Difficulty

## Description

The ** greatest common divisor**, or simply the

**, of two non-negative integers ::a:: and ::b:: is the largest integer that divides both ::a:: and ::b::.**

*gcd*For instance, the greatest common divisor of ::10:: and ::20:: is ::10::. This is often written as ::\text{gcd}(10, 20) = 10::. All common divisors of ::10:: and ::20:: are ::1, 2, 5, 10::, where the largest value is ::10::. Hence, ::\text{gcd}(10, 20) = 10::.

Similarly, ::\text{gcd}(10, 3) = 1::. There is no common divisor of ::10:: and ::3:: except for ::1::, hence, it's the greatest common divisor. Such a pair of integers whose gcd is ::1:: are said to be ** relatively prime** to each other.

As another example, ::\text{gcd}(10, 0) = 10::. On the same lines, ::\text{gcd}(0, 10) = 10:: as well. However, ::\text{gcd}(0, 0):: is undefined. Every integer can divide ::0::, and so likewise there is no limit to this expression.

In this exercise, you have to create a function ** gcd()** that takes in two integers as arguments and returns back their gcd. If both the numbers are

`0`

, the function should return `Infinity`

.You **MUST** implement a brute force algorithm using `for`

that goes over every integer to see if it's a common divisor or not.

Here's an example of the usage of the function:

`gcd(10, 20)`

`gcd(20, 20)`

`gcd(10, 0)`

`gcd(0, 10)`

`gcd(0, 0)`

## New file

Inside the directory you created for this course on JavaScript, create a new folder called **Exercise-22-Greatest-Common-Divisor** and put the .html solution files for this exercise within it.

## Solution

First, let's deal with some simple cases as described below:

- If both the integers are
`0`

, we return`Infinity`

. - If only one integer is
`0`

, we return the other integer.

Here's the implementation of these simple cases:

```
function gcd(a, b) {
if (a === 0 && b === 0) {
return Infinity;
}
if (a === 0 || b === 0) {
return a + b;
}
}
```

If `a === 0 && b === 0`

evaluates to `true`

, that simply means that both `a`

and `b`

are `0`

; likewise we return `Infinity`

.

If this is not the case, then it might be that one of the integers is `0`

. This is checked by the expression `a === 0 || b === 0`

. If it evaluates to `true`

, we return `a + b`

.

Now this is kind of a shortcut. Let's see how.

We know that one of the integers is `0`

and have to return the other one. A quick way is to return the sum of both the numbers, one of which is non-zero. The sum would obviously be that non-zero value which is our gcd.

*So far, so good.*

Next up, if neither of the cases above is met, we move to a loop to perform the computation.

In the loop, we need to iterate upto the minimum of the given arguments `a`

and `b`

(including that value) in search of all common divisors of `a`

and `b`

. Whenever we find one, we update the previously-known common divisor with this new integer. In the end, this common divisor is returned.

Altogether, we get to the following code:

```
function gcd(a, b) {
if (a === 0 && b === 0) {
return Infinity;
}
if (a === 0 || b === 0) {
return a + b;
}
var limit = Math.min(a, b);
var commonDivisor = 1;
for (var i = 2; i <= limit; i++) {
if (a % i === 0 && b % i === 0) {
commonDivisor = i;
}
}
return commonDivisor;
}
```

** limit** holds the upper limit of the loop counter variable

`i`

, which is simply the minimum of the two values `a`

and `b`

. We choose the minimum because if we go higher than that, the smaller of `a`

and `b`

won't be divisible by that larger value.For instance, if `a = 50`

and `b = 1000`

, there is absolutely no point of searching for common divisors of `a`

and `b`

above `50`

since all those numbers won't divide `50`

(which is the minimum value in this case).

The loop goes from `i = 2`

to `i = limit`

in search of common divisors of `a`

and `b`

. The reason why we don't start from `i = 0`

is quite apparent — `0`

can't be a divisor! Moreover, the reason why at `i = 1`

is because we already know that regardless of what integers we choose, `1`

would always be their common divisor.

Whenever a common divisor is noticed, the variable ** commonDivisor** is updated to this new integer. In the end, this integer is the largest common divisor and that's exactly what's returned back by the function.