## 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 `INF`

.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:

```
<?php
echo 'gcd(10, 20): ', gcd(10, 20), "\n";
echo 'gcd(20, 20): ', gcd(20, 20), "\n";
echo 'gcd(10, 0): ', gcd(10, 0), "\n";
echo 'gcd(0, 10): ', gcd(0, 10), "\n";
echo 'gcd(0, 0): ', gcd(0, 0), "\n";
```

## New file

Inside the directory you created for this course on PHP, create a new folder called **Exercise-17-Greatest-Common-Divisor** and put the .php 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`INF`

. - If only one integer is
`0`

, we return the other integer.

Here's the implementation of these simple cases:

```
<?php
function gcd($a, $b) {
if ($a === 0 && $b === 0) {
return INF;
}
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 `INF`

.

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 the integer that is not `0`

, by merely adding `$a`

and `$b`

together (remember that one integer is `0`

, likewise adding them would give us the other integer anyway).

*So far, so good.*

Moving on, if neither of the cases above is met, we move to a loop to perform the gcd computation.

In the loop, starting at the integer `1`

, we ought to iterate up to the minimum of `$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:

```
<?php
function gcd($a, $b) {
if ($a === 0 && $b === 0) {
return INF;
}
if ($a === 0 || $b === 0) {
return $a + $b;
}
$limit = min($a, $b);
$gcd = 1;
for ($i = 2; $i <= $limit; $i++) {
if ($a % $i === 0 && $b % $i === 0) {
$gcd = $i;
}
}
return $gcd;
}
```

** $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`

(the minimum of 50 and 1000) since all those numbers couldn't ever divide `50`

.

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 not 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 ** $gcd** 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.

With this, we've successfully completed the exercise.