Two ways to test for prime numbers in PHP: Sieve and File

by Klaus Graefensteiner 19. February 2010 16:16

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

image 

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.

Tags: , , , ,

Php

Comments

2/22/2010 6:32:13 PM #

OIS

$sqrt = sqrt($number);
return $sqrt == (int)$sqrt;


OIS Norway |

2/23/2010 12:43:21 AM #

Andrew

What about it? The int typecast would strip all decimal places and then the conditional checks if it's the same as the non stripped version.  If so the conditional would return true.  Typecasting maybe isn't the best way to do it though...

Andrew Canada |

2/23/2010 2:09:34 AM #

OIS

Instead of performing the same function (sqrt) on the number twice, the result should be stored in a variable.

OIS Norway |

2/23/2010 12:44:33 AM #

Andrew

Also I love how you're posting about PHP when you use ASP.net on your site Laughing

Andrew Canada |

2/23/2010 1:43:18 AM #

Klaus Graefensteiner

I just started learning PHP. Once I feel comfortable maintaining (debugging) a WordPress blog, then I most likely will migrate my blog to WordPress.

Klaus Graefensteiner United States |

2/26/2010 5:02:54 AM #

pingback

Pingback from websdeveloper.com

Klaus Graefensteiner’s Blog: Two ways to test for prime numbers in PHP: Sieve and File | Webs Developer

websdeveloper.com |

2/26/2010 5:29:26 AM #

pingback

Pingback from developercast.com

Klaus Graefensteiner’s Blog: Two ways to test for prime numbers in PHP: Sieve and File | Development Blog With Code Updates : Developercast.com

developercast.com |

2/26/2010 6:44:48 PM #

Mario

I think you shouldn't use the sieve to test whether a number is prime. The so-called Miller-Rabin test is way more effective (http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test).

Mario Germany |

2/28/2010 1:58:57 AM #

Flex

Don't use a regexp to check for integers, if there are already functions offered by PHP.
ctype_digit or is_numeric will do the job and they are much faster than preg_match.

Flex Germany |

3/1/2010 10:27:34 PM #

pingback

Pingback from traffic-internet.net

Tester les nombres premiers en PHP | traffic-internet.net

traffic-internet.net |

3/2/2010 4:39:35 AM #

pingback

Pingback from vivanno.com

vivanno.com::aggregator  » Archive   » Tester les nombres premiers en PHP

vivanno.com |

Comments are closed

About Klaus Graefensteiner

I like the programming of machines.

Add to Google Reader or Homepage

LinkedIn FacebookTwitter View Klaus Graefensteiner's profile on Technorati
Klaus Graefensteiner

Klaus Graefensteiner
works as Developer In Test and is founder of the PowerShell Unit Testing Framework PSUnit. More...

Open Source Projects

PSUnit is a Unit Testing framwork for PowerShell. It is designed for simplicity and hosted by Codeplex.
BlogShell is The tool for lazy developers who like to automate the composition of blog content during the writing of a blog post. It is hosted by CodePlex.

Administration

About

Powered by:
BlogEngine.Net
Version: 1.6.1.0

License:
Creative Commons License

Copyright:
© Copyright 2014, Klaus Graefensteiner.

Disclaimer:
The opinions expressed herein are my own personal opinions and do not represent my employer's view in any way.

Theme design:
This blog theme was designed and is copyrighted 2014 by Klaus Graefensteiner

Rendertime:
Page rendered at 4/19/2014 10:41:57 PM (PST Pacific Standard Time UTC DST -7)