Exercise: Primality Test

Exercise 9 Easy

Prerequisites for the exercise

  1. PHP Numbers Basics

Objective

Create a function to determine if a given integer is a prime number.

Description

A positive integer greater than ::1:: that is only divisible by two integers, ::1:: and the integer itself, is called a prime number.

For instance, ::2:: is a prime number since it is only divisible by ::1:: and ::2::. So is the integer ::3:: — it's only divisible by ::1:: and ::3::. The first 10 prime numbers are ::2::, ::3::, ::5::, ::7::, ::11::, ::13::, ::17::, ::19::, ::23::, ::29::.

Similarly, a number greater than ::1:: that is divisible by more than 2 integers is called a composite number.

For instance, ::4:: is a composite number since it is divisible by ::1::, ::2:: and ::4::. The first 10 composite numbers are ::4::, ::6::, ::8::, ::9::, ::10::, ::12::, ::14::, ::15::, ::16::, ::18::.

In this exercise, you have to create a function is_prime() that checks whether a given integer is prime or not. Such a function, or algorithm, is usually called a primality testing function.

Here's how the function should look:

function is_prime($n) {
   // Code here...
}

It should return true if the given integer $n is prime, or else false. However, if the given argument is not an integer, or is less than or equal to 1, the function should return NULL.

Below shown is an example usage of the function:

<?php

function is_prime($n) { /* ... */ }

var_dump(is_prime(2));
var_dump(is_prime(3));
var_dump(is_prime(4));
var_dump(is_prime(5));

// Argument is <= 1, hence NULL is returned.
var_dump(is_prime(1));
var_dump(is_prime(0));
var_dump(is_prime(-10));

// Argument is not int, hence NULL is returned.
var_dump(is_prime(2.0));
bool(true) bool(true) bool(false) bool(true) NULL NULL NULL NULL

Hints

Hint 1

Use a for loop to iterate from 2 to $n - 1 in search of a divisor for $n. If a divisor is found, $n is not prime, and if none is found, $n is prime.

View Solution

New file

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.

Solution

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.

Improving the code

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