Objective

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

Difficulty

Easy

Description

The greatest common divisor, or simply the gcd, of two non-negative integers ::a:: and ::b:: is the largest integer that divides both ::a:: and ::b::.

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";
gcd(10, 20): 10 gcd(20, 20): 20 gcd(10, 0): 10 gcd(0, 10): 10 gcd(0, 0): INF
View Solution

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:

  1. If both the integers are 0, we return INF.
  2. 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.