Primality Test Exercise

Inside the directory you created for this course on PHP, create a new folder called Exercise-9-Primality-Test and put the .php solution files for this exercise within it.

In this exercise, we'd create a very elementary primality tester which is not really that efficient.

First off, we start by checking if the given argument is not an integer or is an integer less than or equal to 1. If either of these conditions is true, we simply return NULL.

Let's first implement this:

<?php

function is_prime($n) {
   if (!is_int($n) || $n <= 1) {
      return NULL;
   }
}

See how we use the logical OR (||) operator to check for the truthiness of either of the given conditions.

Good so far.

Next up, we need to divide the number $n one-by-one with consecutive integers starting at 2 and ending right before $n using a for loop.

If at any point, we see that an integer perfectly divides the given number $n, we know that $n can't be a prime and hence return false.

However, if the for loop goes to completion, that means that $n is a prime and likewise we return true outside the loop.

This altogether gives us the following code:

<?php

function is_prime($n) {
   if (!is_int($n) || $n <= 1) {
      return NULL;
   }

   for ($i = 2; $i < $n; $i++) {
      if ($n % $i === 0) {
         // $n has a divisor other than 1 and itself.
         // Hence, return false.
         return false;
      }
   }

   // $n is prime, hence return true.
   return true;
}

The condition $i < $n (in line 8 in the for header) makes sure that we don't set $i to $n because in that case the inner if condition $n % $i === 0 would trivially return true (i.e. $n would obviously divide $n) giving the wrong result.

In the implementation above, we start the search for a divisor of $n from 2 and go all the way up to $n - 1. This surely works but is highly inefficient.

We are performing many redundant checks in this approach. For instance, if $n is 103, we go over the following numbers to find a divisor:

::2::, ::3::, ::4::, ::5::, ::6::, ::7::, ..., ::96::, ::97::, ::98::, ::99::, ::100::, ::101::, ::102::

Now, if you notice carefully, we can clearly reason that any integer above ::10:: won't be able to divide ::103:: unless the corresponding divisor is less than or equal to ::10::.

But how do we know this?

Well, via the square root of ::103:: which is approximately ::10.15::.

It's time for some mathematical knowledge...

Any integer above ::10.15:: has to be multiplied with a number less than or equal to ::10.15:: in order to give ::103:: (only if there is such an integer). There is just no point of going beyond ::10.15:: because if 103 is a composite number, it would anyhow have a divisor less than or equal to ::10.15::.

In other words, for a number ::n::, we only need to search upto (and including) ::\sqrt{n}:: to determine whether ::n:: is prime or not. If there is a divisor of ::n:: less than or equal to ::\sqrt{n}::, ::n:: is a composite number, or else a prime.

Hence, what we can do now is to reduce the upper bound used in the for loop from $n - 1 to the square root of $n.

This is done below:

<?php

function is_prime($n) {
   if (!is_int($n) || $n <= 1) {
      return NULL;
   }

   $limit = (int) ($n ** 0.5);

   for ($i = 2; $i <= $limit; $i++) {
      if ($n % $i === 0) {
         // $n has a divisor other than 1 and itself.
         // Hence, return false.
         return false;
      }
   }

   // $n is prime, hence return true.
   return true;
}

Three things are worth consideration in this code:

1. Firstly, another variable called $limit is introduced in order to cache the square root of $n. We could've used $n ** 0.5 directly inside the header of for but that would recompute this square in each iteration, which is clearly a little bit inefficient.
2. Secondly, we cast the result of $n ** 0.5 to int in order to save time which would've been otherwise spent inside the for loop implicitly coercing $n to a float in order to compare it with $limit.
3. Lastly, the previous < operator comparing $n with the given limit has been replaced with <=. This is because we need to search for a divisor of $n from ::2:: to ::\sqrt{n}::, and this obviously includes $n as well.

And this completes our exercise.

Code on GitHub