3
\$\begingroup\$

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));
}
\$\endgroup\$
1
\$\begingroup\$

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,
  // we add 1.
  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
    // additional slicing needed.
    return i !== null;
  });
}

document.write(getPrimes(121).join(','));

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Thank you so much for your thoughtful answer. I'm sorry I didn't get back to you. After becoming familiar with Clojure here's what I've come up with: \$\endgroup\$ – thomasvarney723 Oct 4 '16 at 22:29
  • \$\begingroup\$ 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); }; } \$\endgroup\$ – thomasvarney723 Oct 4 '16 at 22:30
  • \$\begingroup\$ Here's a link to it (github.com/thomasvarney723/prime-numbers/blob/master/…). I think it's readable but is cripplingly slow compared to both yours and my first attempt. \$\endgroup\$ – thomasvarney723 Oct 4 '16 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.