JS与Haskell埃拉托斯特尼筛法对比及获取前N个质数方案咨询

实现返回前n个质数的函数 #

你原有实现的限制在于预先固定了输入数字序列的上限为n，因此只能返回小于等于n的质数。要实现和Haskell版本类似的灵活调用，我们可以用JavaScript的**Generator（生成器）**模拟懒求值的无限序列，完全对齐Haskell的实现逻辑：

// 无限质数生成器，对应Haskell的 primes 定义
function* primesGenerator() {
  // 从2开始的无限整数序列，对应Haskell的 [2..]
  function* infiniteInts() {
    let num = 2;
    while (true) yield num++;
  }

  // 筛法逻辑，和Haskell版完全对应
  function* sieve(numbers) {
    const first = numbers.next().value;
    yield first;
    // 过滤掉能被first整除的数，递归筛剩下的序列
    yield* sieve((function* filtered() {
      for (const n of numbers) {
        if (n % first !== 0) yield n;
      }
    })());
  }

  yield* sieve(infiniteInts());
}

// 取前n个质数，对应Haskell的 take n primes
function takePrimes(n) {
  const result = [];
  const primeGen = primesGenerator();
  for (let i = 0; i < n; i++) {
    result.push(primeGen.next().value);
  }
  return result;
}

// 取满足条件的质数，对应Haskell的 takeWhile cond primes
function takePrimesWhile(condition) {
  const result = [];
  const primeGen = primesGenerator();
  while (true) {
    const nextPrime = primeGen.next().value;
    if (!condition(nextPrime)) break;
    result.push(nextPrime);
  }
  return result;
}

调用示例：

• 取前1000个质数：takePrimes(1000)
• 取小于1000的所有质数：takePrimesWhile(x => x < 1000)

解决栈溢出问题 #

你原有递归实现的栈溢出是因为递归深度等于质数的个数，当质数数量超过JS引擎的最大调用栈限制时就会报错。
首先要注意：目前只有Safari浏览器实现了ES6标准的尾调用优化，Chrome、Node.js等运行环境都不支持，所以靠尾递归优化无法解决通用场景的栈溢出问题，最稳妥的方案是把递归逻辑改为迭代实现：

// 迭代版无限质数生成器，无栈溢出问题
function* iterablePrimes() {
  const foundPrimes = [];
  let current = 2;
  while (true) {
    // 逻辑等价于递归筛法：只用已找到的质数校验，效率更高
    const isPrime = foundPrimes.every(p => current % p !== 0);
    if (isPrime) {
      foundPrimes.push(current);
      yield current;
    }
    current++;
  }
}

这个迭代版本的逻辑和埃氏筛完全一致，不会产生调用栈累积，即使取前十万个质数也不会出现栈溢出，性能也比递归版本更优。

内容的提问来源于stack exchange，提问作者Pastilhas