通过使用诸如Array#indexOf和 之类Array#splice的线性时间运行的数组操作函数，您正在使 Eratosthenes 的筛选速度变慢。当涉及的两个操作都可以使用 O(1) 时。

以下是遵循传统编程实践的埃拉托色尼筛法：

var eratosthenes = function(n) {
    // Eratosthenes algorithm to find all primes under n
    var array = [], upperLimit = Math.sqrt(n), output = [];

    // Make an array from 2 to (n - 1)
    for (var i = 0; i < n; i++) {
        array.push(true);
    }

    // Remove multiples of primes starting from 2, 3, 5,...
    for (var i = 2; i <= upperLimit; i++) {
        if (array[i]) {
            for (var j = i * i; j < n; j += i) {
                array[j] = false;
            }
        }
    }

    // All array[i] set to true are primes
    for (var i = 2; i < n; i++) {
        if(array[i]) {
            output.push(i);
        }
    }

    return output;
};

你可以在n = 1 000 000这里看到一个活生生的例子。

这个问题在定义什么是“大数字”时有点吝啬，并接受它从大约一百万开始，目前的答案适用；然而，它使用了相当多的内存，因为每个要筛选的元素使用一个 8 字节数（64 位的双实数），每个找到的素数使用另一个 8 字节数。该答案不适用于大约 2.5 亿及以上的“大量”，因为它会超过 JavaScript 执行机器可用的内存量。

以下实现 Eratosthenes 的“无限”（无界）页面分段筛选的 JavaScript 代码克服了这个问题，因为它只使用一个位打包的 16 KB 页面分段筛选缓冲区（一位代表一个潜在的质数），并且只使用存储基数直到当前页段中当前最大数的平方根，实际找到的素数按顺序枚举，无需任何存储；还可以通过仅筛选奇数复合物来节省时间，因为唯一的偶数素数是 2：

var SoEPgClass = (function () {
  function SoEPgClass() {
    this.bi = -1; // constructor resets the enumeration to start...
  }
  SoEPgClass.prototype.next = function () {
    if (this.bi < 1) {
      if (this.bi < 0) {
        this.bi++;
        this.lowi = 0; // other initialization done here...
        this.bpa = [];
        return 2;
      } else { // bi must be zero:
        var nxt = 3 + 2 * this.lowi + 262144; //just beyond the current page
        this.buf = [];
        for (var i = 0; i < 2048; i++) this.buf.push(0); // faster initialization 16 KByte's:
        if (this.lowi <= 0) { // special culling for first page as no base primes yet:
          for (var i = 0, p = 3, sqr = 9; sqr < nxt; i++, p += 2, sqr = p * p)
            if ((this.buf[i >> 5] & (1 << (i & 31))) === 0)
              for (var j = (sqr - 3) >> 1; j < 131072; j += p)
                this.buf[j >> 5] |= 1 << (j & 31);
        } else { // other than the first "zeroth" page:
          if (!this.bpa.length) { // if this is the first page after the zero one:
            this.bps = new SoEPgClass(); // initialize separate base primes stream:
            this.bps.next(); // advance past the only even prime of 2
            this.bpa.push(this.bps.next()); // keep the next prime (3 in this case)
          }
          // get enough base primes for the page range...
          for (var p = this.bpa[this.bpa.length - 1], sqr = p * p; sqr < nxt;
            p = this.bps.next(), this.bpa.push(p), sqr = p * p);
          for (var i = 0; i < this.bpa.length; i++) { //for each base prime in the array
            var p = this.bpa[i];
            var s = (p * p - 3) >> 1; //compute the start index of the prime squared
            if (s >= this.lowi) // adjust start index based on page lower limit...
              s -= this.lowi;
            else { //for the case where this isn't the first prime squared instance
              var r = (this.lowi - s) % p;
              s = (r != 0) ? p - r : 0;
            }
            //inner tight composite culling loop for given prime number across page
            for (var j = s; j < 131072; j += p) this.buf[j >> 5] |= 1 << (j & 31);
          }
        }
      }
    }
    //find next marker still with prime status
    while (this.bi < 131072 && this.buf[this.bi >> 5] & (1 << (this.bi & 31))) this.bi++;
    if (this.bi < 131072) // within buffer: output computed prime
      return 3 + ((this.lowi + this.bi++) * 2);
    else { // beyond buffer range: advance buffer
      this.bi = 0;
      this.lowi += 131072;
      return this.next(); // and recursively loop just once to make a new page buffer
    }
  };
  return SoEPgClass;
})();

上面的代码可用于通过以下 JavaScript 代码计算达到给定限制的素数：

window.onload = function () {
  var elpsd = -new Date().getTime();
  var top_num = 1000000000;
  var cnt = 0;
  var gen = new SoEPgClass();
  while (gen.next() <= top_num) cnt++;
  elpsd += (new Date()).getTime();
  document.getElementById('content')
    .innerText = 'Found ' + cnt + ' primes up to ' + top_num + ' in ' + elpsd + ' milliseconds.';
};

如果将上述两段 JavaScript 代码放入与以下名为whatever.html 的 HTML 代码位于同一文件夹中的名为 app.js 的文件中，您将能够通过打开其中的 HTML 文件在浏览器中运行该代码：

<!DOCTYPE html>

<html lang="en">
  <head>
    <meta charset="utf-8" />
    <title>Page Segmented Sieve of Eratosthenes in JavaScript</title>
    <script src="app.js"></script>
  </head>
  <body>
    <h1>Page Segmented Sieve of Eratosthenes in JavaScript.</h1>

    <div id="content"></div>
  </body>
</html>

当在使用即时 (JIT) 编译的 JavaScript 执行引擎（例如 Google Chrome 的 V8 引擎）上运行时，此代码可以筛选到 10 亿的范围，即几十秒。通过使用极限轮分解和对最低基本素数的页面缓冲区的预剔除可以实现进一步的收益，在这种情况下，执行的工作量可以进一步减少四倍，这意味着可以计算素数的数量在几秒钟内高达 10 亿（计数不需要这里使用的枚举，而是可以直接在页段缓冲区上使用位计数技术），尽管以增加代码复杂性为代价。

编辑_添加：

通过使用 TypedArray 和 ECMAScript 2015 中的 asm.js 优化（现在所有常见浏览器都支持），执行速度可以提高三倍或更多，代码修改如下：

"use strict";
var SoEPgClass = (function () {
  function SoEPgClass() {
    this.bi = -1; // constructor resets the enumeration to start...
    this.buf = new Uint8Array(16384);
  }
  SoEPgClass.prototype.next = function () {
    if (this.bi < 1) {
      if (this.bi < 0) {
        this.bi++;
        this.lowi = 0; // other initialization done here...
        this.bpa = [];
        return 2;
      } else { // bi must be zero:
        var nxt = 3 + 2 * this.lowi + 262144; // just beyond the current page
        for (var i = 0; i < 16384; ++i) this.buf[i] = 0 >>> 0; // zero buffer
        if (this.lowi <= 0) { // special culling for first page as no base primes yet:
          for (var i = 0, p = 3, sqr = 9; sqr < nxt; ++i, p += 2, sqr = p * p)
            if ((this.buf[i >> 3] & (1 << (i & 7))) === 0)
              for (var j = (sqr - 3) >> 1; j < 131072; j += p)
                this.buf[j >> 3] |= 1 << (j & 7);
        } else { // other than the first "zeroth" page:
          if (!this.bpa.length) { // if this is the first page after the zero one:
            this.bps = new SoEPgClass(); // initialize separate base primes stream:
            this.bps.next(); // advance past the only even prime of 2
            this.bpa.push(this.bps.next()); // keep the next prime (3 in this case)
          }
          // get enough base primes for the page range...
          for (var p = this.bpa[this.bpa.length - 1], sqr = p * p; sqr < nxt;
            p = this.bps.next(), this.bpa.push(p), sqr = p * p);
          for (var i = 0; i < this.bpa.length; ++i) { // for each base prime in the array
            var p = this.bpa[i] >>> 0;
            var s = (p * p - 3) >>> 1; // compute the start index of the prime squared
            if (s >= this.lowi) // adjust start index based on page lower limit...
              s -= this.lowi;
            else { // for the case where this isn't the first prime squared instance
              var r = (this.lowi - s) % p;
              s = (r != 0) ? p - r : 0;
            }
            if (p <= 8192) {
              var slmt = Math.min(131072, s + (p << 3));
              for (; s < slmt; s += p) {
                var msk = (1 >>> 0) << (s & 7);
                for (var j = s >>> 3; j < 16384; j += p) this.buf[j] |= msk;
              }
            }
            else
              // inner tight composite culling loop for given prime number across page
              for (var j = s; j < 131072; j += p) this.buf[j >> 3] |= (1 >>> 0) << (j & 7);
          }
        }
      }
    }
    //find next marker still with prime status
    while (this.bi < 131072 && this.buf[this.bi >> 3] & ((1 >>> 0) << (this.bi & 7)))
      this.bi++;
    if (this.bi < 131072) // within buffer: output computed prime
      return 3 + ((this.lowi + this.bi++) << 1);
    else { // beyond buffer range: advance buffer
      this.bi = 0;
      this.lowi += 131072;
      return this.next(); // and recursively loop just once to make a new page buffer
    }
  };
  return SoEPgClass;
})();

加速是有效的，因为它使用预先类型化的 ECMAScript 原始数组，通过直接在数组中使用整数来避免开销（也通过使用浮点表示避免浪费空间），并且还使用使用 asm.js 的可用类型提示来导致位操作使用无符号整数/字节。同样，为了节省数组分配的时间，它现在分配筛分数组一次，并为每个新页面段将其归零。现在，它在低端 1.92 Gigahertz CPU 上在大约 16 秒内筛选到 10 亿，而不是大约 50 秒。同样，该算法经过修改以简化内部合数表示（以位打包位），以提高较小素数的速度，这是大部分剔除操作。

请注意，现在大约 60% 的时间花费在枚举找到的素数上。对于通常使用这种筛子来计算找到的素数的情况，这可以大大减少，只需对每个段页的数组中的零位数求和即可。如果这样做，那么在这个低端 CPU 上筛选到 10 亿的时间将接近 7 秒，并且可能还有其他一些优化（所有时间都使用 Google Chrome 版本 72 V8 JavaScript 引擎，该引擎不断改进和更高版本可能运行得更快）。

TBH，我个人不喜欢 JavaScript 的所有扩展和复杂性，这些扩展和复杂性是使其成为“现代”语言所必需的，特别是不喜欢动态类型，因此在几年前出现时接受了 Microsoft 的 TypeScript。上面的代码实际上是对作为 TypeScript 输出的代码的修改，同时强调了静态类型的面向对象编程 (OOP)。我突然想到，通过向“原型”添加方法的标准方式调用“下一个”实例方法可能比仅调用函数慢得多，因此我对其进行了测试，发现情况确实如此，使用这个 runnable通过将枚举更改为简单的输出闭包函数，链接枚举找到的素数的速度大约快两倍半。

现在，我们可以通过仅计算找到的素数的数量来完全消除素数枚举，如另一个带有修改代码的可运行链接所示，表明即使进行了上述改进，找到的素数的枚举仍然花费几乎与实际做的时间一样多的时间用这种算法筛选可以确定枚举时间作为上述两个链接到可运行代码的运行时间之间的差异。

请注意，链接的运行时间将与我在此处提到的不同（并且可能更短），因为大多数当前的 CPU 将比我目前使用的平板电脑 Windows CPU（英特尔 x5-Z3850，频率为 1.92 Gigahertz 和JavaScript 在您查看链接的机器上运行。

这使得 JavaScript 只比在 JVM 或 DotNet 上实现的相同算法慢一点，当然这仍然比从 C/C++、Rust、Nim、Haskell、Swift 等语言编译的高度优化的本机代码慢得多， FreePascal、Julia 等可以在这个低端 CPU 上运行该算法大约两秒钟。根据浏览器的实现，WebAssembly 可以比这里的 JavaScript 快两到三倍地运行这个算法；同样，当 WebAssembly 规范完全完成并实施时，我们将获得多线程支持，以通过使用的有效内核数量来进一步提高收益。

END_EDIT_ADD

EDIT_ADD_MORE_AND_LATER_EVEN_MORE：

一旦完成上述相当小的修改以有效地计算找到的素数而不是枚举它们，从而使计数时间与筛选它们相比是一个很小的开销，则值得进行更广泛的更改以使用最大轮因式分解（不仅 2 表示“仅赔率”，而且 3、5 和 7 表示覆盖 210 个潜在素数的轮子），并且还预先剔除小筛选阵列的初始化，因此没有必要通过以下 11、13、17 和 19 的素数剔除。当使用页面分段筛选时，这将合数剔除操作的数量减少了大约 4 到 10 亿的范围，并且由于每次剔除操作减少了大约与上述代码的速度相同。

有效地进行 210 跨度轮分解的方法是遵循这种有效地进行“仅赔率”筛分的方法：上述当前算法可以被认为是从两个平面中筛出一个位填充平面，而另一个平面可以消除，因为它只包含两个以上的偶数；对于 210 跨度，我们可以定义这种大小的 48 位打包数组，表示 11 及以上的可能素数，其中所有其他 162 个平面包含的数字是 2、3、5 或 7 的因数，因此不需要被考虑。通过这种方式，以较少的内存要求进行筛选同样有效（与“仅几率”相比提高了一半以上，并且与此处的效率一样高，其中一个 48 平面“页面”表示 16 千字节 = 每平面 131072 位乘以 210，范围为 27,525，

虽然上面描述的扩展代码有几百行而且很长，在这里发布，但它可以在我使用 Google V8 JavaScript 引擎的低端 Intel 1.92 Gigahertz CPU 上在不到两秒的时间内计算出 10 亿的素数，大约为 4比在本机代码中运行的相同算法慢五倍。这是关于我们在 JavaScript 中可以做的事情的限制，“循环展开”和（当然）多处理等更先进的技术不可用。不过，在这台低端CPU上几乎可以匹配Sieve of Atkin的手工优化参考C实现，运行时间约为1.4秒。

补充： 我已经在另一个 StackOverflow 答案中用一个可运行的片段更详细地解释了这一点，并在该线程的其他答案中交叉链接。

尽管上面的代码在大约 160 亿的范围内非常有效，但其他改进可以帮助将效率保持在数万亿的更大范围内，这样人们就可以在几个小时内计算出大约 1e14 的素数数量。在更快的 CPU 上使用 JavaScript 的日子。这很有趣，因为这个范围内的素数数量直到 1985 年才知道，然后由数值分析技术确定，因为当时的计算机不够强大，无法在该范围内以足够快的速度运行 Eratosthenes 筛网。合理的时间。

由于我目前的“反 JavaScript”和专业函数式编码风格偏见，我将使用 Fable 编写此代码，它是 F#（静态类型的 ML“函数”语言，如果需要，也支持 OOP）的实现，可以非常转换为 JavaScript有效地使得生成的代码可能与直接用 JavaScript 编写的代码一样快。

为了表明代码在使用 Fable（带有 Elmish React 接口）的 Chrome V8 JavaScript 引擎中的运行速度几乎与上面最后一个链接中编写纯 JavaScript 的速度一样快，这里是包含上述算法的 Fable 在线 IDE 的链接. 它的运行速度比纯 JavaScript 稍微慢一些，并且 JavaScript 输出“代码”视图显示了原因：为尾调用优化 (TCO) 生成的代码对于 JavaScript 来说并不是一个简单的循环——它很容易手动调整代码仅用于紧密的内部剔除循环以获得相同的速度。代码除了数组内容的变化和序列生成器函数的需要外，均采用函数式编写，与JavaScript的形式相同，便于理解；如果代码的这个流生成器部分被编写为使用 F# 序列，没有可见的变化，它的工作速度也会一样快。

由于上面的 Fable 代码是纯 F#，它也可以作为来自 DotNet Core 的 JavaScript 生成器与 Fabulous 库一起运行，或者直接在 DotNet Core 下运行它可以运行多平台并且速度更快。

END_EDIT_ADD_MORE_AND_EVEN_MORE

总之，有各种各样的算法可以在一秒的数量级内找到几百万的素数，但是需要一个高效的基于页面分段数组的埃拉托色尼筛算法来确定按执行时间顺序排列的十亿的素数.

我会将此作为对亚历山大的评论发布，但我没有这样做的声誉。他的回答很棒，这只是对其进行了调整以使其更快。我通过测试 n = 100,000,000 进行基准测试。

我没有在“数组”中使用 true 和 false，而是通过使用 1 和 0 获得了很大的速度提升。这将我在 Chrome 中的时间从 5000 毫秒减少到 4250 毫秒。Firefox 不受影响（5600 毫秒）。

然后我们可以考虑到偶数永远不会是素数。立即将 2 放入“输出”中，您可以执行 i=3；i += 2，并且 j += i*2 在筛选过程中（我们可以跳过偶数倍数，因为任何数乘以偶数都是偶数），只要我们在推到“输出”时也 i += 2结尾。这将我在 Chrome 中的时间从 4250 毫秒减少到 3350 毫秒。Firefox 受益较少，从 5600 毫秒下降到 4800 毫秒。

无论如何，这两个调整的结合使我在 Chrome 中的速度提高了 33%，在 Firefox 中提高了 14%。这是亚历山大代码的改进版本。

var eratosthenes = function(n) {
    // Eratosthenes algorithm to find all primes under n
    var array = [], upperLimit = Math.sqrt(n), output = [2];

    // Make an array from 2 to (n - 1)
    for (var i = 0; i < n; i++)
        array.push(1);

    // Remove multiples of primes starting from 2, 3, 5,...
    for (var i = 3; i <= upperLimit; i += 2) {
        if (array[i]) {
            for (var j = i * i; j < n; j += i*2)
                array[j] = 0;
        }
    }

    // All array[i] set to 1 (true) are primes
    for (var i = 3; i < n; i += 2) {
        if(array[i]) {
            output.push(i);
        }
    }

    return output;
};

只是为了好玩，我严格按照 TDD 的规则实现了 Erastoten 筛算法（使用 Node 运行）。这个版本应该足够面试了，作为学校练习或者就像我一样 - 有点乱。

让我声明，我绝对认为公认的答案应该是 GordonBGood 提供的答案。

module.exports.compute = function( size )
{
    if ( !utils.isPositiveInteger( size ) )
    {
        throw new TypeError( "Input must be a positive integer" );
    }

    console.time('optimal');
    console.log();
    console.log( "Starting for optimal computation where size = " + size );
    let sieve = utils.generateArraySeq( 2, size );

    let prime = 2;
    while ( prime )
    {
        // mark multiples
        for ( let i = 0; i < sieve.length; i += prime )
        {
            if ( sieve[i] !== prime )
            {
                sieve[i] = -1;
            }
        }

        let old_prime = prime;
        // find next prime number
        for ( let i = 0; i < sieve.length; i++ )
        {
            if ( ( sieve[i] !== -1 ) && ( sieve[i] > prime ) )
            {
                prime = sieve[i];
                break;
            }
        }

        if ( old_prime === prime )
        {
            break;
        }
    }
    console.timeEnd('optimal');
    // remove marked elements from the array
    return sieve.filter( 
        function( element )
        {
            return element !== -1;
        } );
} // compute

我会感谢任何有意义的批评。

整个存储库可以在我的 github 帐户中找到。

因为我参加聚会有点晚了。我想添加我的简单而有点hacky的贡献，它可以找到最多100的所有质数：

<!DOCTYPE html>
<html>
<title>Primes</title>
<head>
<script>
function findPrimes() {
    var primes = []
    var search = []

    var maxNumber = 100
    for(var i=2; i<maxNumber; i++){
        if(search[i]==undefined){
            primes.push(i);
            for(var j=i+i; j<maxNumber; j+=i){
                search[j] = 0;
            }
        }
    }
   document.write(primes);
}
findPrimes();
</script>
</head>
<body>
</body>
</html>