快速创建大量质数流

Question

我一直在应对编码挑战。说明如下：

“创建无穷无尽的质数流 - 有点像 IntStream.of(2,3,5,7,11,13,17)，但无限（嗯，很长）。流必须能够在几秒钟内产生 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提出了一个有道理的观点，上面的方法确实效率太低了，可以改进。这让我四处寻找实现他建议的布尔数组方法的最有效解决方案，这让我找到了 Matt Gibson 的 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));

快速创建大量质数流

Creating a large stream of prime numbers fast

optimization

primes

node.js