在JavaScript中运行Eratosthenes算法的Sieve对大量运行无穷无尽

Question

我一直在尝试用JavaScript 编写Sieve of Eratosthenes算法.基本上我只是遵循以下步骤:

1. 创建从2到(n-1)的连续整数列表
2. 设第一个素数p等于2
3. 从p开始,以p为增量计数并删除每个数字(p和p的倍数)
4. 转到列表中的下一个数字并重复2,3,4
5. 将无意删除的素数添加回列表

这就是我想出的:

function eratosthenes(n){
var array = [];
var tmpArray = []; // for containing unintentionally deleted elements like 2,3,5,7,...
var maxPrimeFactor = 0;
var upperLimit = Math.sqrt(n);
var output = [];

// Eratosthenes algorithm to find all primes under n

// Make an array from 2 to (n - 1)
//used as a base array to delete composite number from
for(var i = 2; i < n; i++){
    array.push(i);
}

// Remove multiples of primes starting from 2, 3, 5,...
for(var i = array[0]; i < upperLimit; i = array[0]){
    removeMultiples: 
    for(var j = i, k = i; j < n; j += i){
        var index = array.indexOf(j);
        if(index === -1)
            continue removeMultiples;
        else
            array.splice(index,1);
    }
    tmpArray.push(k);
}
array.unshift(tmpArray);
return array;
}

它适用于小数字,但不适用于大于一百万的数字.我使用Node.js进行测试,这个过程似乎无穷无尽,并且没有出现内存错误.我在这里阅读了一个解决方案(也在javascript中),但仍然无法完全理解它.

问题:如何使这项工作足够大,如一百万及以上？

Answer 1

你是通过利用数组操作功能,例如使埃拉托塞尼有意较慢的筛Array#indexOf和Array#splice其以线性时间运行.当你可以为所涉及的两个操作都有O(1)时.

以下是传统编程实践后的Eratosthenes筛选:

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这里看到一个实例.

Answer 2

这个问题在定义"大数"是什么的时候有点吝啬,并且接受它只有大约一百万的开头,目前的答案是有效的; 但是,对于要筛分的每个元素,它使用一个8字节数(一个64位的双实数)和每个找到的素数的另一个8字节数,使用相当多的内存.这个答案不适用于大约2.5亿及以上的"大数",因为它会超过JavaScript执行机器可用的内存量.

实现Eratosthenes的"无限"(无界)页面分段筛的以下JavaScript代码克服了这个问题,因为它只使用一个比特打包的16千字节页面分段筛分缓冲区(一位表示一个潜在的素数)并且仅使用存储器base在当前页面段中填充当前最高数字的平方根,实际找到的素数按顺序枚举,无需任何存储; 只通过筛选奇数复合材料来节省时间,因为唯一的素数是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代码放入名为app.js的文件中,该文件位于与以下名为whatever.html的HTML代码相同的文件夹中,则可以通过在其中打开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)编译(如Google Chrome的V8引擎)在JavaScript执行引擎上运行时,此代码可以筛选到十亿秒的范围是几十秒.通过使用极限轮分解和预先剔除最低基本素数的页面缓冲区可以实现进一步的增益,在这种情况下,执行的工作量可以再减少四倍,这意味着可以计算素数的数量在几秒钟内高达十亿(计数不需要这里使用的枚举,而是可以直接在页面段缓冲区上使用位数查找表),但代价是增加了代码复杂性.

Answer 3

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

我没有在'array'中使用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;
};