Codewars: Prime Streaming (PG-13)

Question

I'm timing out on Codewars' Prime Streaming kata. Below is my code:

"use strict";

let _base = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71];
let _bufferSize = 1000

class Primes {
   static get base() {
      return _base;
   }

   static get bufferSize() {
      return _bufferSize;
   }

   static set bufferSize (value) {
      _bufferSize = value;
   }

   static sieve(array) {
      for (let p of Primes.base) {
         array = array.filter(n => n % p !== 0);
      }
      return array;
   }

   static sieve_2(array) {

   }

   static * stream() {
      const candidates = [];
      for (let i = 73; i < 5001; i += 2)
         candidates.push(i);
      Primes.base.push(...Primes.sieve(candidates));
      const buffer = Primes.base.slice();

      while (true) {
         let current;
         while (buffer.length > 0) {
            current = buffer.shift();
            yield current;
         }
         let [lower, upper] = [current + 2, current + Primes.bufferSize];
         let basket = [];
         for (let i = lower; i <= upper; i += 2)
            basket.push(i);
         buffer.push(...Primes.sieve(basket));
      }
   }
}

As far as I can tell, changing the buffer size affected nothing. I first generate primes less than 5001 because their upper bound on primes they test is somewhere below 16 million, and I wasn't enthused about doing the investigation work to find a precise bound, so I just went with a loose one.

Answer 1

Your current code, if I understand it, starts by sieving each target without recognizing that if the target is less than the highest cache (or _base) then it is prime if and only if it in the cache.

One option is to keep your primes in a single cache (_base), make sure that the cache is high as your target, and check if your target is in your cache.

The rough code would have only two functions: one ensures that base array is high enough, and the other returns the value. Something like:

const primes = [2, 3, 5];

function ensure_primes(until_n) {
    let n = primes.slice(-1) + 1;
    while (n <= until_n) {
        if (primes.every(prime => n % prime != 0)) {
            primes.push(n)
        }
        n += 1;
    }
}

function is_prime(target) {
    ensure_primes(target);
    return target in primes
}

Is this what you were asking?