PHP Function To Detect A Prime Number

Thursday, April 9, 2009 - 10:28

A prime number is a number which has exactly two distinct number divisors: 1 and itself. So if you take the number 11, it can only be divided to get a whole number if it is divided by 1 or 11. If any other number is used then a fraction is always found.

The following function uses a method called trial division to detect if a number is prime or not.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function is_prime($number)
{
    // 1 is not prime
    if ( $number == 1 ) {
        return false;
    }
    // 2 is the only even prime number
    if ( $number == 2 ) {
        return true;
    }
    // square root algorithm speeds up testing of bigger prime numbers
    $x = sqrt($number);
    $x = floor($x);
    for ( $i = 2 ; $i <= $x ; ++$i ) {
        if ( $number % $i == 0 ) {
            break;
        }
    }
    
    if( $x == $i-1 ) {
        return true;
    } else {
        return false;
    }
}

The function first detects if the number is 1 (not prime) or if it is two (prime). These are two exceptions to the rules that follow and must be caught before proceeding. The function divides the number by all numbers less than or equal to the square root of that number. If any of the divisions come out as an integer, then the original number is not a prime. Otherwise, it is a prime.

Here is an example bit of script that finds all of the prime numbers between 0 and 1,000,000.

1
2
3
4
5
6
7
8
9
$start = 0;
$end =   1000000;
for($i = $start; $i <= $end; $i++)
{
    if(is_prime($i))
    {
        echo '<strong>'.$i.'</strong>, ';
    }
}

Obviously this takes a little while to run!

Also, this function is only useful if you want to check integers, if your number is higher than the maximum value of an integer PHP will use a float to store the number, which causes false positives. To find the maximum value of an integer on your system use the following code.

echo PHP_INT_MAX;
Category: 
philipnorton42's picture

Philip Norton

Phil is the founder and administrator of #! code and is an IT professional working in the North West of the UK.
Google+ | Twitter

Comments

thanks for that it was very helpful !!!

philipnorton42's picture
Submitted by philipnorton42 on Tue, 06/25/2013 - 15:12

You just need to loop through the array and and run is_prime() on each number, storing the value that is the highest.

Thanks for sharing this information with us, good article.

Add new comment