node.js - 快速创建大量素数流

Question

我一直在致力于编码挑战。说明如下:

“创建一个无尽的素数流 - 有点像 IntStream.of(2,3,5,7,11,13,17)，但是无限的(好吧，long)。该流必须能够在几秒钟内产生 2500 万个素数”

我的代码生成素数，但速度不够快；它总是超时。我希望有人能够为我提供一些关于如何优化解决方案或找到更好的解决方案的指导。我的代码如下。这是我一段时间以来第一次在这里发帖，所以如果我需要做任何不同的事情或需要澄清，请告诉我。谢谢。

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;
}

Answer 1

正如 rossum 在评论中建议的那样，您可以使用 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 提出了一个有效的观点，上述方法确实效率太低，可以改进。这促使我四处寻找实现他建议的 bool 数组方法的最有效的解决方案，这使我找到了 this answer马特·吉布森:

"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));