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
$limit
is introduced in order to cache the square root of$n
. We could've used$n ** 0.5
directly inside the header offor
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
toint
in order to save time which would've been otherwise spent inside thefor
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.