PHP Function To Detect A Prime Number

9th April 2009 - 3 minutes read time

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

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

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;

 

Comments

Permalink
thanks for that it was very helpful !!!

Tom (Fri, 05/17/2013 - 16:36)

Permalink
Can you write for me a PHP function (a function named largestPrime() that returns the largest prime number in an array)

Set Kyar Wa Lar (Tue, 06/25/2013 - 10:39)

Permalink
You just need to loop through the array and and run is_prime() on each number, storing the value that is the highest.
Permalink
Thanks for sharing this information with us, good article.

Jail (Tue, 09/12/2017 - 19:18)

Add new comment

The content of this field is kept private and will not be shown publicly.