How do I calculate all prime numbers with a really large max in the browser using JSFiddle

Question

I am working on some of the typical katas for JS and I came across one that wanted all the primes for a really large number. I tried the following in JSFiddle.

findPrimes(max){
   let dont = [], primes = [];
   for (var i = 2; i <= max; i++) {
     if (!dont[i]) {
       primes.push(i);
       for (var j = i; j <= max; j += i) dont[j] = true;
     }
   }
}

This works relatively good till about this.findPrimes(51475143);, however, if I try say... this.findPrimes(851475143); I get a sad face an the JS engine appears to crash. I know I could probably do straight V8 and squeeze a bit out and maybe even go toward a C-based node module but to keep things simple I would like to keep it in the browser if possible. If not and proof can be provided I will accept that answer.

Answer 1

The problem you're having is likely due to running out of memory, with your dont array being the culprit. Luckily, since it's just an array of booleans, you can do the same thing with a bit array, which will save some space.

JavaScript doesn't have any native bit array type, but you can simulate one by storing an array of 32-bit numbers and using bitwise operators to retrieve or set the desired bit. So something like:

class BitArray {
  constructor(len) {
    this.arr = Array(Math.ceil(len / 32)).fill(0)
  }

  set(i) {
    const j = Math.floor(i / 32)
    this.arr[j] = this.arr[j] | (1 << (i % 32))
  }

  get(i) {
    const j = Math.floor(i / 32)
    return (this.arr[j] & (1 << (i % 32))) && 1 || 0;
  }
}

Then, with that alone, you can run your snippet and get a result (although it takes a while):

class BitArray {
  constructor(len) {
    this.arr = Array(Math.ceil(len / 32)).fill(0)
  }

  set(i) {
    const j = Math.floor(i / 32)
    this.arr[j] = this.arr[j] | (1 << (i % 32))
  }

  get(i) {
    const j = Math.floor(i / 32)
    return (this.arr[j] & (1 << (i % 32))) && 1 || 0;
  }
}

function findPrimes(max) {
  const dont = new BitArray(max)
  const primes = [];
  for (var i = 2; i <= max; i++) {
    if (!dont.get(i)) {
      primes.push(i);
      for (var j = i * 2; j <= max; j += i) dont.set(j);
    }
  }

  return primes;
}

const primes = findPrimes(851475143);
console.log("Done. Max Prime:", primes[primes.length - 1])
console.log("And last 10 primes:", primes.slice(-10))

However, in addition to that, you can do a few more optimizations to your sieve:

• You can start j at i*i instead of just i, since any number less than that will have a smaller prime than i as a factor already (and thus, will already have been set in dont).
• You really only need to check odd numbers as part of the sieve, so you can change the outer loop to increment by 2 each time (i += 2 instead of i++), and then change the inner loop to increment by i*2 instead of i (since j + i*(odd) is always even).

Using those, you can change your snippet to:

class BitArray {
  constructor(len) {
    this.arr = Array(Math.ceil(len / 32)).fill(0)
  }

  set(i) {
    const j = Math.floor(i / 32)
    this.arr[j] = this.arr[j] | (1 << (i % 32))
  }

  get(i) {
    const j = Math.floor(i / 32)
    return (this.arr[j] & (1 << (i % 32))) && 1 || 0;
  }
}

function findPrimes(max) {
  const dont = new BitArray(max / 2)  // Only need half the memory, since we only check odds.
  const primes = [2];                 // We already know 2 is prime
  for (var i = 3; i <= max; i += 2) { // Start at 3, increment by 2, so only odds are checked.
    if (!dont.get((i-1)/2)) {         // The (i-1)/2 converts each odd to it's "halfway" number
      primes.push(i);
      for (var j = i*i; j <= max; j += i*2) dont.set((j-1)/2);
    }
  }

  return primes;
}

const primes = findPrimes(851475143);
console.log("Done. Max Prime:", primes[primes.length - 1])
console.log("And last 10 primes:", primes.slice(-10))

As you can see, you get the same result for the last 10 primes, and, at least anecdotally, it seems to run quite a bit faster.