A few weeks ago, during a job interview, I was asked to implement an algorithm to find if a certain number is prime or not, so I decided to discuss here a possible solution to this problem.

First of all, one needs to understand clearly what is a prime number. According to WolframAlpha (http://www.wolframalpha.com/input/?i=what+is+a+prime+number):

A prime number is a positive integer having exactly one positive divisor other than one

Following the definition, to find if $num is prime, a first approach to this problem could be to check every number in the interval [2, $num -1], and this can be done with a snippet like:

<?php
for($i = 2; $i < $num; $i++) {
   //if $i is a divisor of $num, then the number is not prime
   if($num % $i == 0) {
      return false;
   }
}
return true;
?>

This approach works, but it is terribly ineffective for large values of $num.

As a next step, we can see that if $num is not divisible by the smallest even value, that is 2, we do not need to check the other even values, because it would not be divisible by them either. So we can check first if $num is divisible by 2 and then by odd values bigger than 2:

<?php
   //check the first even number
   if($num % 2 == 0)
      return false;

    //check the odd values
    for($i = 3; $i < $num; $i = $i + 2) {
       if($num % $i == 0) {
          return false;
       }
    }
?>

Now it’s also possible to note that we don’t need to check all the odd numbers in the range [3, $num], we can stop at $num / 2, because $num/($num / 2) = 2, so dividing $num by any number bigger than $num / 2 would give us a number smaller than 2, and that’s not a possible factor.

If we think better about the problem, it’s even possible to notice that we don’t need to reach $num / 2 in the cycle, we just need to go to the square root of $num, that’s because if n = ab is composite number (with a and b != 1) then one of the factors a or b is necessarily at most sqrt(n) (http://en.wikipedia.org/wiki/Prime_number#Trial_division).

All in all, we can create a complete function to find if a general number is a prime number:

<?php
/**
 * Checks if $num is a Prime Number
 * @param int $num
 * @return boolean
 */
function isPrime($num) {
    //1 is not prime. See: http://en.wikipedia.org/wiki/Prime_number#Primality_of_one
    if($num == 1)
        return false;

    //2 is prime (the only even number that is prime)
    if($num == 2)
        return true;

    /**
     * if the number is divisible by two, then it's not prime and it's no longer
     * needed to check other even numbers
     */
    if($num % 2 == 0) {
        return false;
    }

    /**
     * Checks the odd numbers. If any of them is a factor, then it returns false.
     * The sqrt can be an aproximation, hence just for the sake of
     * security, one rounds it to the next highest integer value.
     */
    for($i = 3; $i <= ceil(sqrt($num)); $i = $i + 2) {
        if($num % $i == 0)
            return false;
    }

    return true;
}

?>

Hope this will be helpful to you.

Bookmark and Share