« Prime number detector: brute force method | Home | Unix philosophies applied to general programming »
Prime number detector: sieve method
By Sparky | December 7, 2005
As promised I have implemented an Eratosthenes Sieve algorithm for prime number detection. This method differs from the brute force method in that rather than detecting if a given number is prime, it detects all primes up to n. Basically you step through an array removing all multiples of known primes starting from the bottom up. If a number has not been removed from the array it must be prime.
$step = 2; //initialize our counter
while ($step <= $totest):
if ($sieve[$step] == true) { //if this number is prime then
for ($multiples = ($step * 2); $multiples <= $totest; $multiples = $multiples + $step){
$sieve[$multiples] = false; //set all multiples of $step to non-prime
}
}
$step++; //increment $step and begin again
endwhile;
I added a simple bit of code to let the viewer select if they want to see the prime numbers alone, or highlighted amongst the entire array of numbers. I’m playing around with the ability to make the list of numbers wrap at the square root of n but that’s a little dodgy at the moment.
This is getting easier and easier. Next I’m going to tackle databases and start doing some MySQL work. I have a lot of plans and ideas for customizing SugarCRM but that will require me being back in the swing of things with RDBMS technology.
Topics: Development, Technology |