CODEWITHSUNDEEP
node.jsoptimizationprimes
KevinKCHDev
KevinKCHDev

Reputation: 23

Creating a large stream of prime numbers fast

I have been working on a coding challenge. The instructions are as follows:

"Create an endless stream of prime numbers - a bit like IntStream.of(2,3,5,7,11,13,17), but infinite ( well, long ). The stream must be able to produce 25 million primes in seconds"

My code generates prime numbers but not fast enough; it keep timing out. I was hoping someone might be able to give me some guidance on how to optimize my solution or find a better one. My code is below. This is my first time posting on here in a while, so if I need to do anything differently or clarification is needed please let me know. Thank you.

class Primes {
  static * stream() {
  yield 2; 
  let n = 3;
   while (n < 15486042) {
     if (isPrime(n)) {yield n}
     n += 2;
   }
  }
}

function isPrime(n) {
  for (let a = 3; a <= ~~Math.sqrt(n); a+=2) {
    if (n%a == 0) return false;
    }
  return true;
}

Upvotes: 2

Views: 1985

Answers (2)

vitaly-t
vitaly-t

Reputation: 25890

The stream must be able to produce 25 million primes in seconds

The following can produce 25 mln primes in under 2 seconds:

import {generatePrimes} from 'prime-lib';

const start = Date.now();

const primes = [...generatePrimes({boost: 25_000_000})];

console.log(Date.now() - start); //=> < 2000ms

Here's the implementation source.

Upvotes: 0

Michael Rodriguez
Michael Rodriguez

Reputation: 2176

As rossum suggested in the comments, you can use the Sieve of Eratosthenes

function getPrimes(limit) {

  let primes = [];
  let toCheck = Array.from(Array(limit + 1).keys()).splice(2);

  while (toCheck.length) {
    primes.push(toCheck.shift());
    toCheck = toCheck.filter(
      function(i) {
        return i % primes[primes.length - 1] !== 0;
      }
    );
  }

  console.log(primes);

}

getPrimes(10000);

James Reinstate Monica Polk raised a valid point, the above method is indeed much too inefficient and can be improved. This led me to look around for the most efficient solution that implements the boolean array method he suggested, which led me to this answer by Matt Gibson:

"use strict";
function findPrimes(n){
  
  function primeSieve(g,o,r){
    var t = (Math.sqrt(4+8*(g+o))-2)/4,
        e = 0,
        s = 0;
    
    ar.fill(true);
    if (o) {
      for(var i = Math.ceil((o-1)/3); i < (g+o-1)/3; i++) ar[1+3*i-o] = false;
      for(var i = 2; i < t; i++){
        s = Math.ceil((o-i)/(1+2*i));
        e = (g+o-i)/(1+2*i);
        if (i%3-1) for(var j = s; j < e; j++) ar[i + j + 2*i*j-o] = false;
      }
    } else {
        for(var i = 1; i < (g-1)/3; i++) ar[1+3*i] = false;
        for(var i = 2; i < t; i++){
          e = (g-i)/(1+2*i);
          if (i%3-1) for(var j = i; j < e; j++) ar[i + j + 2*i*j] = false;
        }
      }
    for(var i = 0; i < g; i++) ar[i] && r.push((i+o)*2+1);
    return r;
  }
  
  var cs = n <= 1e6 ? 7500
                    : n <= 1e7 ? 60000
                               : 100000, // chunk size
      cc = ~~(n/cs),                     // chunk count
      xs = n % cs,                       // excess after last chunk
      ar = Array(cs/2),                  // array used as map
  result = [];
  
  for(var i = 0; i < cc; i++) result = primeSieve(cs/2,i*cs/2,result);
  result = xs ? primeSieve(xs/2,cc*cs/2,result) : result;
  result[0] *=2;
  return result;
}


var primes = [];
console.time("primes");
primes = findPrimes(15486042);
console.timeEnd("primes");
console.log(primes.length);
console.log(primes.splice(0, 1000));

Upvotes: 1

Related Questions