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.