The sieve of Erastosthenes is *that* other way of computing prime numbers you may have heard from internet - you know, the one that's efficient. As many other things named in the form of <weird noun> of <really weird person name>, it dates back to ancient Greece and is attributed to the eponymous mathematician, Erastosthenes of Cyrene.
The algorithm does its work by "marking" all the multiples of each prime number it finds up to a limit. For example, 2 is the very first prime. When the algorithm finds 2, it saves that value in a box called 'prime numbers' while marking all its multiples (4, 6, 8, and so on) with a big X on top. When the program see this mark on a number it simply ignores them.
There's a very common implementation of this algorithm that uses two arrays, one for marks and one for the numbers, respectively, and two loops. Let's see how this looks on JavaScript.
** Common (imperative) algorithm
*** JavaScript
function prime(max) {
let isPrime = new Array(max).fill(true);
let nPrimes = [];
isPrime[0] = false;
isPrime[1] = false;
for (let i = 2; i < max; ++i) {
if (isPrime[i]) {
nPrimes.push(i);
for (let j = i * i; j < max; j += i) {
isPrime[j] = false;
}
}
}
return nPrimes;}
isPrime is an array of size /max/ containing boolean values. We init it with true values and immediately assign false to the two first positions. If a certain member of isPrime of index i is true, we push its index to the nPrimes array. Then, with another loop, we put all members of isPrime whose index is a multiple of i to false.
A dry run for prime numbers between 0 and 5 would look like this:
prime(6)
isPrime = new Array(6).fill(true)
nPrime = []
isPrime[0] = false
isPrime[1] = false
if (isPrime[2])
true
nPrime.push(2)
isPrime[4] = false
if (isPrime[3])
true
nPrime.push(3)
if (isPrime[4])
false
if (isPrime[5])
true
nPrime.push(5)
[2, 3, 5]
Fun. Thing is, look at all those mutations! There's a lot of assignment and pushing values into arrays. This isn't a bad thing per se, but it makes this implementation painful to port to functional languages like Haskell or Scheme, where this is not idiomatic. So we need another approach.
** An approach
In the code above we went from an empty array to a filled one, what if we try the opposite? After all, getting new arrays by applying filters to other arrays is much more common in functional languages than pushing and popping.
So, how we go about it? Let's first model what we want:
Having this array a_1: [ 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
We want a_2: [ 2, 3, 5, 7 ]
Now we have reduced the issue to find a filter that makes a_2 from a_1.
** The filter
First, let's create a filter to remove all multiples of two from a_1. We know, thank God, that any x, x being a number, for which x % 2 = 0 is true is a multiple of two. So let's try it
[ 2, 3, 4, 5, 6, 7, 8, 9, 10 ].filter( x => x % 2 != 0 )
Which gives us:
[ 3, 5, 7, 9 ]
Good, but not quite! Notice it left out the 2 itself and that's not what we want. So let's add a rule to our filter to leave poor two alone.
[ 2, 3, 4, 5, 6, 7, 8, 9, 10 ].filter( x => x % 2 != 0 || x == 2 )
Which gives us:
[ 2, 3, 5, 7, 9 ]
Now applying the same filter with 3 instead of 2
[ 2, 3, 5, 7, 9 ].filter( x => x % 3 != 0 || x == 3 )
[ 2, 3, 5, 7 ]
Success! We went from a_2 to a_1. By using this filter, replacing two by the next number and so on, we get the desired functionality. Now, on to devise a function to automatize all the boring stuff :)
** The function
We applied succesive filters whose only difference was a number, so we can generalize it as follows:
filter( x => x % i != 0 || x == i )
** Examples
*** Ruby
*** Haskell
*** JavaScript
*** Go
*** Scheme
(define (prime lst cnt)
(let ((test (lambda (x) (or (not (= (modulo x cnt) 0)) (= x cnt)))))
(if (not (< cnt (length lst)))
lst
(prime (filter test lst) (+ cnt 1)))))
