0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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?

| improve this answer | |
\$\endgroup\$

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.