# Sieve of Eratosthenes using a Javascript array

Any feedback on my code would be greatly appreciated.

/*
The Sieve of Eratosthenes using a javascript array as
an associative data structure.
*/

function range(start, limit, step) {
var rangeArray = [];
for (var i = start; i < limit; i += step)
rangeArray.push(i);
return rangeArray;
}

function isNotNull(value) { // predicate for filtering
if (value !== null)
return true;
else
return false;
}

function nullMultiples(multiple, array) { // mutates array
var step = multiple;
while (multiple < array.length) {
array[multiple] = null;
multiple = multiple + step;
}
}

function nextPrime(currentPrime, array) {
var successor = currentPrime++;
while (array[successor] === null)
successor++;
return successor;
}

function primes(below) {
var initSet = range(0, below, 1);
var primeSet = []; // set of numbers used as a multiple
var currentPrime = initSet[2]; // the first multiple is 2
while (currentPrime < Math.sqrt(initSet.length)) {
primeSet.push(currentPrime);
nullMultiples(currentPrime, initSet); // mutate initSet
currentPrime = nextPrime(currentPrime, initSet);
}
// return the numbers that were used as multiples and all
// inidicies that still contain a number, except 0 and 1
return primeSet.concat(initSet.slice(2).filter(isNotNull));
}


Since you're just doing steps of 1 and starting with 0, we don't need to take account for those. Your range function can be simplified into the following.

function range(length){
return Array.apply(null, Array(length)).map(function (_, i) {return i;});
}


Also, a comparison is already a boolean by itself. So your isNotNull could be simplified into the following. We could coerce value into a boolean by using !!, since we're working with numbers, we might encounter 0 which is falsy but technically not null. So we compare explicitly with null instead to avoid this.

function isNotNull(value) {
return value !== null;
}


You could also inline your search for the next prime into your primes function. You can simply check your number list if the next number has been nulled, and if so, have the loop in primes skip the number.

With that (and hopefully my understanding of the algorithm isn't wrong), here's my take:

function range(length) {
return Array.apply(null, Array(length)).map(function(_, i) { return i; });
}

function getPrimes(end) {

// We get the numbers below the square root of the limit. The | 0 is
// dropping the decimal info, and since range here is zero-indexed,
return range((Math.sqrt(end) | 0) + 1).reduce(function(numbers, root, index) {

// If the number at root is null, then its multiples may have been
// nulled by an earlier prime. We bail out. Nothing to do here.
if (numbers[root] === null) return numbers;

// We null every multiple, provided it's not 0 and 1
else if (root !== 0 && root !== 1)
for (var i = root * root; i < numbers.length; i += root)
numbers[i] = null;

// If we reached here, then probably you're looking at 0 or 1
else numbers[root] = null;

return numbers;

// Here's the array that generates 0-to-end. Again, range is
// zero-indexed so the + 1 is necessary.
}, range(end + 1)).filter(function(i) {

// Since 0 and 1 are already nulled, they will fall off here. No
document.write(getPrimes(121).join(','));
• function primesLessThan(n) { var composites = range(3, Math.sqrt(n), 2) .map(function(x) { return range(x * x, n, x); }) .reduce(concat); var data = [2].concat(range(3, n, 2)); return data.filter(doesNotContain(composites)); } function range(start, end, step) { var result = []; for(var i = start; i < end; i += step) result.push(i); return result; } function concat(a, b) { return a.concat(b); } function doesNotContain(arr) { return function(elem) { return !(arr.indexOf(elem) > -1); }; } – thomasvarney723 Oct 4 '16 at 22:30