In PHP is really no ideal way to test large integers and determine whether they are prime numbers or not. The most popular algorithm for finding prime numbers is a memory and resource hog. It is called The Sieve of Eratosthenes.

Besides the Sieve I also implemented a prime number test by initializing an array of prime numbers from a file that contains the first 100,000 prime numbers. This is of course much faster, but would require files that contain all prime numbers up to a specific large number. The files of course could be partitioned, which would also increase performance.

Sieve of Erastosthenes on YouTube

Here is the algorithm described in words (from Wikipedia)

To find all the prime numbers less than or equal to a given integer n  by Eratosthenes' method:

   1. Create a list of consecutive integers from two to n: (2, 3, 4, ..., n),
   2. Initially, let p equal 2, the first prime number,
   3. While enumerating all multiples of p starting from p2, strike them off from the original list,
   4. Find the first number remaining on the list after p (it's the next prime); let p equal this number,
   5. Repeat steps 3 and 4 until p2 is greater than n.
   6. All the remaining numbers in the list are prime.

Here is an example (from wikipedia)

First generate a list of integers from 2 to 30:

  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Strike out the multiples of 2 from the original list starting from 4, resulting in:

  2  3     5     7     9    11    13    15    17    19    21    23    25    27    29

The first number in the list after 2 is 3; strike out the multiples of 3 from the
original list starting from 9, to get:

  2  3     5     7          11    13          17    19          23    25          29

The first number in the list after 3 is 5; strike out the multiples of 5 from the
original list starting from 25:

  2  3     5     7          11    13          17    19          23                29

The first number in the list after 5 is 7, but 7 squared is 49 which is greater
than 30 so the process is finished. The final list consists of all the prime numbers
less than or equal to 30.

Number tests in PHP

My PHP function library provides besides the prime tests some other functions like:

• IsPalindrome
• IsInteger (uses regular expression to test whether a string is a valid integer)
• IsEven
• IsPositive
• IsPerfectSquare
• IsPalindromicPrime

<?php
	function IsInteger($number)
	{
		$result = preg_match('/^-?[0-9]+$/', $number, $matches);
		return $result;
	}

	function IsEven($number)
	{
		return (($number % 2) == 0);
	}
	
	function IsPositive($number)
	{
		return $number >= 0;
	}
	
	function IsPerfectSquare($number)
	{
		return sqrt($number) == (int)sqrt($number);
	}
	
	function IsPalindrome($number)
	{
		return $number == strrev($number);
	}
	
	function PrimesFromErathosthenes($number)
	{
        $number = $number + 2; //Otherwise the actual number wouldn't be included in array of numbers
		$nlist = array();
        $sqrt = ceil(sqrt($number));

        $nlist[] = 2;
        $nlist[] = 3;
        for($i = 5 ; $i < $number ; $i += 2)
        {
            if($i % 3 != 0)
            {
                $nlist[] = $i;
            }
        }
        
        for($i=2,$divisor=5; $divisor < $sqrt ; $i++) 
        {
            $count = count($nlist);
            $j = $i*$i;
            $nlist2 = array_slice($nlist,0,$j);
            
            for( ; $j < $count ; $j++)
            {
                $num = $nlist[$j];
                if($num % $divisor != 0)
                {
                    $nlist2[] = $num;
                }
            }
            unset($nlist);
            $nlist = $nlist2;
            $divisor = $nlist[$i+1];
        }
        
        $primes = $nlist;
        return $primes;
	}
	
	function IsPrime($number, $primeSource, $displayOption)
	{
		if(!IsInteger($number))
		{ 
			return false;
		} 
		else 
		{ 
			$number = (int) $number;
		}
		if(IsEven($number)){return false;}
		
		$primes;
		
		$IsInPrimesArray = false;
		
		if($primeSource == 'Sieve')
		{
			$primes = PrimesFromErathosthenes($number);
			if(in_array($number, $primes))
			{
				$IsInPrimesArray = true;
			}
			else
			{
				$IsInPrimesArray = false;	
			}
		}
		
		if($primeSource == 'File')
		{
			$primes = GetFirst100000PrimesFromFile();
			$number = "$number"."\r\n";
			if(in_array($number, $primes))
			{
				$IsInPrimesArray = true;
			}
			else
			{
				$IsInPrimesArray = false;
			}
		}
		
		if($displayOption == 'ShowPrimes')
		{
			echo "primes ".implode(" ", $primes)."<br />";
		}
		
		return $IsInPrimesArray;
	}
	
	function IsPalindromicPrime($number, $primeSource, $displayOption)
	{
		if(!IsPositive($number) || $number > 1318699)
		{
			return false;
		}
		if(!IsPalindrome($number))
		{
			return false;
		}
		else
		{
			if(IsPrime($number, $primeSource, $displayOption))
			{
				return true;
			}
			else
			{
				return false;
			}
		}
	}
	
	function GetFirst100000PrimesFromFile()
	{
		$primes = file('First100000Primes.txt');
		return $primes;
	}
	
?>

Download

The download contains besides the functions library a web form and the file with the 100,000 pre-calculated prime numbers: PrimesWIthSieveAndFromFile.zip

Ausblick

That’s it.