## Objective

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

## Difficulty

## 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));
```

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

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

- Firstly, another variable called
is introduced in order to cache the square root of`$limit`

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

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