2

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;
}
KevinKCHDev
  • 23
  • 5
  • 1
    Use the Sieve of Eratosthenes. If necessary use it in chunks. If that is not fast enough, then try the Sieve of Atkin, which is slightly faster. – rossum Dec 20 '19 at 20:26
  • You're testing every single number for prime by checking every possible divisor up through the square root. If you can store prior primes, you only have to test the prime divisors up to the square root (basically, the Sieve of Eratosthenes). – lurker Dec 20 '19 at 20:27
  • @rossum - Thanks, I've looked into trying the Sieve of Atkin. It seems more complicated but perhaps it's the way to go. – KevinKCHDev Dec 22 '19 at 04:40
  • @lurker - Thank you for pointing that out. I based this solution on the Sieve of Eratosthenes, though I know this falls far short of an ideal optimization. So to optimize I should pass the array of primes to the isPrime(n) function and use that as a jumping point to assess? Thank you again. – KevinKCHDev Dec 22 '19 at 04:42
  • @rossum no, Atkin is never faster than properly wheel-factorized (and segmented) sieve of Er-. – Will Ness Dec 22 '19 at 16:29
  • @lurker there's no divisibility testing for primality in the Sieve of Eratosthenes, none whatsoever. :) primes are found for free between composites, which are generated by repeated additions from primes: `primes = [2 ..] \ [[p*p, p*p+p ..] for p in primes]` (in pseudocode). – Will Ness Dec 22 '19 at 16:31
  • @KevinKCHDev check out some examples, [in Python](https://stackoverflow.com/a/10733621/849891), and [in general](https://stackoverflow.com/a/12563800/849891). – Will Ness Dec 22 '19 at 16:41
  • @WillNess I think you're misunderstanding my comment. As you already know, the Sieve of Erostothenese eliminates multiples of previously established primes. I was pointing out that the Op isn't eliminating multiples of previously established primes, but just looping through odd numbers. That's all I was saying. – lurker Dec 22 '19 at 17:08
  • @lurker it's just that your comment could be misconstrued as saying that testing by primes below sqrt *is* the S. of Er. (if one ignores the "basically" qualification there). Just wanted to clarify that it's still not the proper one, for the sake of a random visitor to these pages. :) – Will Ness Dec 22 '19 at 17:15
  • 1
    @WillNess I see. That's definitely not what I intended. That's the problem with these terse little comments. :p – lurker Dec 22 '19 at 17:33

2 Answers2

1

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));
Michael Rodriguez
  • 2,142
  • 1
  • 9
  • 15
  • 1
    This is an example of a Sieve of Eratosthenes, but I don't think this will be efficient enough for OP. A much more common and efficient approach is to fill an array S with truth values, then for each prime p mark S[2*p], S[3*p], ... as false. You don't need to perform any remainder/mod (%) operations or create new arrays. – President James K. Polk Dec 21 '19 at 20:33
  • 1
    Good point, I actually would have never thought to do that myself. – Michael Rodriguez Dec 21 '19 at 20:52
  • Wow fantastic! I would not have thought to break it down this way. Thank you both. – KevinKCHDev Dec 23 '19 at 17:59
0

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.

vitaly-t
  • 24,279
  • 15
  • 116
  • 138