Recursive Sieve of Eratosthenes

in code


Call me stupid, but the Sieve defeated me for years-I could never quite seem to make it click.

TL;DR: Return the first element of the array, joined with the rest of the array with all multiples of the first element removed. A non-zero value is truthy in JavaScript, which is coerced into true, so non-multiples are kept.

function sieve(arr) {
    if (!arr.length || arr[0] >= Math.sqrt(arr[arr.length - 1])) {
        return arr;
    } else {
        return [arr[0], ...sieve(arr.filter(n => n % arr[0]))];
    }
}

I used the range() function described here to generate the array.

sieve(range(2, 10)); // [ 2, 3, 5, 7]

This method is fun, but it chokes and dies for values > ~10000 because you’re throwing around a big fuck-off stack. I’m sure there are language that optimize these kinds of recursive calls, but JavaScript isn’t one.



A Summer of Running

in running

Achill Half Marathon

in running


Your email address will not be published. Required fields are marked *