What is a prime number?
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers (Wikipedia). By that definition, then, 2,3 and 5 are prime numbers, but 4 and 6 (both being the product of of two smaller numbers) are not.
Note also that 1 is excluded from the prime numbers by definition. Although it was once includedas a prime number, it is now excluded because it's inclusion requires that other statements have to be worded to exclude it. The subject of this article, The Sieve of Eratosthenes, would fail if 1 were prime because very number greater than 1 would be excluded as a multiple of 1.
The Sieve of Eratosthenes
The basic algorithm is to take a list of numbers from 2 to the upper limit of the range you're searching, then work up from 2, striking out every multiple, leaving just the original number. Repeat for 3, and so on until you reach the top of the range. When you're done, any number that remains is prime.
If we're searching for primes up to 20, the first pass this will delete 4, 6, 8, 10, 12, 14, 16, 18 and 20. The second pass will delete 6, 9, 12, 15 and 18. When we've completed our search we'll be left with 2,3,5,7,11,13,17 and 19.
Optimisations
The naive algorithm above obviously searches some numbers many times. It also searches more numbers than it needs. We can improve execution time by optimising:
- Search multiples only as far as the square root of the limit. Any factor larger than the square root will have a corresponding factor less than the square root, and thus will have been eliminated already.
- Repeat the multiples search only for the numbers that have not already been eliminated. This avoids searching for multiples of 4, since they will already have been struck out as a multiple of 2, and so on
- Start the search for each multiple from the square of the number you're searching. For example, start the search for 3 at 9, since all multiples of 3 less than that (only 6) will have been eliminated as a multiple of a lower number.
- Mark each number s found, rather than deleting it from the list. This reduces the overhed in reorganising the list
The improved algorithm
Taking these optimisations gives us this algorthm:
Create list of numbers from 2 to target limit.
Search list for next available prime - call this F
if F is less than square root of limit
Starting at F2 mark F2,F2+F,F2+2F, etc up to the limit.
Repeat from top
else
Finish search
Delete marked numbers from list, to leave list of primes.
An implementation in PHP
/**
* Eratosthenes_class.php
*
* @author Mike Whipps
* @copyright Copyright (c) 2021 Mike Whipps, littlevale.com
*/
class Eratosthenes {
private $startTime;
private $stopTime;
private array $numList;
public function __construct(int $range) {
// For timing
$this->startTime = hrtime(true);
// Create an empty array to store the sieve.
// Length set to store numbers from 1 to range.
$this->numList = array_fill(2, $range-1, true);
// Start at the first prime (1 is not prime!)
$nextPrime = 2;
// Stop searching at sqrt(limit)
$searchLimit = sqrt($range);
// Search until we reach the square root of the limit.
while ($nextPrime < $searchLimit) {
// Start at nextPrime squared, and mark each multiple false
for ($i = $nextPrime ** 2; $i <= $range; $i += $nextPrime) {
$this->numList[$i] = false;
}
// Now look for the next unmarked number - the next prime
while (!($this->numList[++$nextPrime]) && $nextPrime < $searchLimit) {}
}
// For timing
$this->stopTime = hrtime(true);
}
/**
* Return a list of the elements we haven't marked in the search
*
* @return array
*/
public function getPrimes(): array {
// array_filter() removes all the false values.
// Then array_keys() gets the actual prime numbers that are left.
return array_keys(array_filter($this->numList));
}
/**
* Return a measure of the time taken, in milliseconds
*
* @return float
*/
public function getElapsedTime():float {
return ($this->stopTime-$this->startTime)/1000000;
}
}
An implementation in Javascript
/**
* Finding prime numbers: An implementation of the sieve of Eratosthenes.
*
* @copyright Copyright (c) 2021, Mike Whipps
* @Author Mike Whipps
* @licence MIT Licence
*/
class Eratosthenes {
constructor(range) {
// For timing
this.startTime = Date.now();
// Create an empty array to store the sieve.
// Length set to store numbers from 1 to range.
this.numList = new Array(range+1);
this.numList.fill(true, 2, range+1);
// Start at the first prime (1 is not prime!)
let nextPrime = 2;
// Stop searching at sqrt(limit)
let searchLimit = Math.sqrt(range);
// Search until the square root of the range
while (nextPrime < searchLimit) {
// Start at nextPrime squared, and mark each multiple true
for (let i = nextPrime ** 2; i <= range; i += nextPrime) {
this.numList[i] = false;
}
// Now look for the next unmarked number - the next prime
while(!this.numList[++nextPrime] && nextPrime<searchLimit) {}
}
// for timing
this.stopTime = Date.now();
}
/**
* Return a list of the elements we haven't marked in the search
*/
getPrimes(){
let primeList = [];
this.numList.forEach((e,ix)=>{if (e){primeList.push(ix);}})
return primeList;
}
getElapsedTime(){
return this.stopTime-this.startTime;
}
}