## Check if a number is a prime number

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.

2 is prime

My distraction. I’ve corrected the code. Thanks for your comment.

the prog runs perfectly thanks

the condition “$i the condition will become $i which will not work for numbers higher than 3 (it will always return false because once the number is divided by itself — which is a pre-condition of a prime number — it will return false).

I didn’t get very well what you were trying to say, can you reformulate your comment please? I tested my code snippet again and it is working fine… For instance, it returns true for the number 5 and false for the number 9… Try it yourself…

Thanks for nice explanation:)

Thanks a lot for your comment.

What about Sieve of Eratosthenes??? Here there’s a PHP implementation:

http://es.wikibooks.org/wiki/Implementaci%C3%B3n_de_algoritmos_de_teor%C3%ADa_de_n%C3%BAmeros/Criba_de_Erat%C3%B3stenes#PHP

it can also like this

<?php for($i=1;$i<=100;$i++){

$a = 0;

for($j=1;$j<=$i;$j++){

if($i % $j == 0){

$a++;

}

}

if($a == 2){

echo $i.'’;

}

}

?>

You could write it that way, I think it’s not a very good solution. You would never know what number to use instead of ’100′ in the limit for the first for cycle… And the method you use runs all numbers, even when you know that your value is not divisible by 2…

Near the end, where you have:

for($i = 3; $i 2; $i–) {

In your example, you calculate the sqrt on every iteration, rather than only once. For large numbers, this accounts for a massive amount of time.