Eratosthenes算法在JavaScript中的大规模无休止运行

vwhgwdsa  于 2023-03-21  发布在  Java
关注(0)|答案(9)|浏览(112)

我一直在尝试用JavaScript编写Sieve of Eratosthenes算法。基本上我只是按照下面的步骤进行：
1.创建从2到（n-1）的连续整数列表
1.设第一个素数p等于2
1.从p开始，以p为增量向上计数，并删除其中的每个数字（p和p的倍数）
1.转到列表中的下一个数字，重复2，3，4
1.将无意删除的质数添加回列表
这就是我的结论

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

它适用于小数字，但不适用于大于100万的数字。我使用Node.js进行测试，过程似乎无穷无尽，没有显示内存错误。我读过一个解决方案here（也是JavaScript），但仍然不能完全理解它。
问题：如何使这个工作足够大的数字，如100万和以上？

JavaScript

9条答案

按热度按时间
zpf6vheq

zpf6vheq1#

使用数组操作函数，如Array#indexOf和Array#splice，可以使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;
};

You can see a live example for n = 1 000 000 here.

赞(0）分享  回复(0）举报  2023-03-21
gwbalxhn

gwbalxhn2#

这个问题在定义什么是“大数字”时有点小气，并接受它仅从大约100万开始，current answer适用于此;然而，它使用了相当多的内存，因为每个要筛选的元素都有一个8字节的数字（64位的双真实的），每个找到的素数都有另一个8字节的数字。这个答案对于大约2.5亿或更高的“大数字”不起作用，因为它会超过JavaScript执行机器可用的内存量。
下面的JavaScript代码实现了“无限”Eratosthenes的（无界）页分段筛选克服了该问题，因为它仅使用一个位压缩的16千字节页分段筛选缓冲器（一个比特表示一个潜在的素数）并且仅使用用于直到当前页段中的当前最高数的平方根的基本素数的存储，其中实际找到的素数按顺序枚举而不需要任何存储;由于仅有的偶数素数是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>

当在使用Just-In-Time的JavaScript执行引擎上运行时，这段代码可以在几十秒内筛选到十亿范围可以通过使用极端轮因式分解和对最低基素数的页面缓冲区的预剔除来实现进一步的增益，在这种情况下，所执行的工作量可以被进一步削减四倍。这意味着素数的数量可以在几秒内计数到十亿（计数不需要这里使用的枚举，而是可以直接在页段缓冲器上使用位计数技术），尽管代价是增加了代码复杂性。

编辑_添加：

通过使用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千兆赫CPU上在大约16秒内筛选到十亿，而不是大约50秒。同样，修改该算法以简化内部复合数表示（以位压缩位的形式），从而对于较小的素数具有额外的速度，这是挑选操作的主要部分。
注意，现在大约60%的花费时间花费在仅枚举所找到的素数上。对于这种筛子的通常使用，这可以大大减少，以便仅通过仅对每个段页的阵列中的零位的数目求和来仅计数所找到的素数。如果这样做，在这种低端CPU上，筛选到10亿的时间接近7秒，可能还有其他一些优化（所有计时都使用Google Chrome版本72 V8 JavaScript引擎，该引擎正在不断改进，后续版本可能会运行得更快）。
TBH，我个人不喜欢JavaScript的所有扩展和复杂性，这些都是使其成为“现代”语言所必需的，特别是不喜欢动态类型，几年前微软的TypeScript出现时，我就接受了它。上面的代码实际上是对TypeScript输出代码的修改沿着同时强调了静态类型的面向对象编程（OOP）。我突然想到，通过向“原型”添加方法的标准方式调用“下一个”示例方法可能比仅仅调用一个函数慢得多，所以我测试了一下，发现确实如此this runnable link枚举找到的素数的速度大约是2.5倍，只需将枚举更改为简单的输出闭包函数。
现在，我们可以通过计算找到的素数的数量来完全消除素数枚举，如this other runnable link with modified code所示，这表明即使有了上述改进，找到的素数的枚举仍然花费几乎与使用该算法实际进行筛选一样多的时间，其中能够将枚举时间确定为上述两个链接到可运行代码的运行时间之间的差。

请注意，链接的运行时间将与我在这里提到的不同（并且可能更短），因为大多数当前的CPU将比我目前使用的平板电脑Windows CPU更快，更强大（Intel x5-Z3850在1.92千兆赫兹，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段。这将使用页面分段筛选时的复合数字剔除操作的数量减少了约四倍到十亿的范围，并且可以被写入使得其由于页面分段筛选而以约四倍的速度运行。减少了操作，其中每个剔除操作的速度与上述代码的速度大致相同。
有效地进行210跨度轮因式分解的方法是遵循这种有效地进行“仅奇数”筛选的方法：上述当前算法可以被认为是从两个平面中筛选出一个比特压缩平面，其中另一个平面可以被消除，因为它只包含大于2的偶数;对于210跨度，我们可以定义48个这种大小的位压缩阵列，其表示11及以上的可能素数，其中所有其他162个平面包含是2，3，5，或者七个，因此不需要考虑。以这种方式，筛选内存需求更少同样有效（与“仅奇数”相比减少了一半以上，并且效率与这里一样高，其中一个48平面“页”表示16千字节=每平面131072位乘以210，其是每筛页段27，525，120个数字的范围，因此，只有40个页段被筛选到十亿（而不是如上所述的几乎四千个），并且因此每个页段每个基素数的起始地址计算的开销更小，以进一步提高效率。
虽然上面描述的扩展代码有几百行，而且很长，但它可以在我的低端Intel 1.92 GHz CPU上使用Google V8 JavaScript引擎在两秒内将素数的数量计数到10亿，这比在本地代码中运行相同的算法慢大约四到五倍。这是我们在JavaScript中可以做的极限，然而，它几乎足以匹配在这个低端CPU上运行的手工优化的参考C实现的Atkin的Sieve，其运行时间约为1.4秒。

**补充：**我已经解释了更详细的with a runnable snippet in another StackOverflow answer，并在交叉链接的其他答案，该线程。

虽然上述代码在高达约160亿的范围内是相当有效的，其他改进可以帮助将效率保持到甚至更大的范围，即几万亿，使得可以在几天内在更快的CPU上使用JavaScript来计数素数的数量，直到大约1 e14。直到1985年才知道，然后通过数值分析技术确定，因为当时的计算机没有足够的功能来在合理的时间内运行Eratosthenes筛。
以我目前的“反JavaScript”和亲函数式编码风格的偏见，我会使用Fable来编写这段代码，Fable是F#（静态类型ML“函数式”语言，如果需要，也支持OOP）的实现，它可以非常有效地转换为JavaScript，这样生成的代码可能与直接用JavaScript编写的代码一样快。

为了证明使用Fable（带有Elmish React接口）的代码在Chrome V8 JavaScript引擎中的运行速度几乎与上面最后一个链接中编写纯JavaScript一样快，这里是一个包含上述算法的Fable在线IDE的链接。它的运行速度比纯JavaScript略慢，JavaScript输出“Code”视图显示了原因：Tail Call Optimizations（TCO）生成的代码并不像JavaScript那样是一个简单的循环--为了获得相同的速度，很容易手动调整内部紧密剔除循环的代码。代码是以函数式风格编写的，除了数组内容突变和序列生成器函数所必需的，它们与JavaScript的形式相同，以便于理解;如果代码的这个流生成器部分被编写为使用F#序列，则它将工作得差不多快，而没有可见的突变。
由于上面的Fable代码是纯F#的，它也可以作为DotNet Core的JavaScript生成器与Fabulous库一起运行，或者可以通过直接在DotNet Core下运行来运行多平台和更快一点。

END_EDIT_ADD_MORE_AND_EVEN_MORE

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

赞(0）分享  回复(0）举报  2023-03-21
xoshrz7s

xoshrz7s3#

我想把这个作为评论发给 Alexandria ，但我没有这样做的声誉。他的答案很棒，这只是为了让它更快。我通过测试n = 100，000，000进行了基准测试。
我没有在“数组”中使用true和false，而是使用1和0来大大提高速度。这将我在Chrome中的时间从5000毫秒减少到4250毫秒。Firefox不受影响（无论哪种方式都是5600毫秒）。
然后我们可以考虑偶数永远不会是质数。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;
};
赞(0）分享  回复(0）举报  2023-03-21
zqdjd7g9

zqdjd7g94#

只是为了好玩，我严格按照TDD的规则实现了Erastoten sieve算法（用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

我会欣赏任何有意义的批评。
The whole repository can be found on my github account.

赞(0）分享  回复(0）举报  2023-03-21
p4tfgftt

p4tfgftt5#

function sieveOfEratosthenes(num, fromSt = null) {
let boolArr = Array(num + 1).fill(true); // Taking num+1 for simplicity
boolArr[0] = false;
boolArr[1] = false;

for (
    let divisor = 2;
    divisor * divisor <= num;
    divisor = boolArr.indexOf(true, divisor + 1)
)
    for (let j = 2 * divisor; j <= num; j += divisor) boolArr[j] = false;

let primeArr = [];
for (
    let idx = fromSt || boolArr.indexOf(true);
    idx !== -1;
    idx = boolArr.indexOf(true, idx + 1)
)
    primeArr.push(idx);

return primeArr;
}
赞(0）分享  回复(0）举报  2023-03-21
2w2cym1i

2w2cym1i6#

该算法每100万次只需要几毫秒（ok 2 - big test # time=498.815ms）：

module.exports.fast = function eratosthenes (max) {
  let sqrt = Math.sqrt(max)
  let sieve = new Array(max).fill(0)

  for (let primeCandidate = 2; primeCandidate < sqrt; primeCandidate++) {
    if (sieve[primeCandidate] === true) {
      continue // already processed
    }
    for (let multiple = primeCandidate * primeCandidate; multiple < max; multiple += primeCandidate) {
      if (sieve[multiple] === 0) {
        sieve[multiple] = true
      }
    }
  }

  return sieve
    .map((isPrime, i) => ({ i, isPrime })) // find the number associated with the index
    .filter(({ i, isPrime }) => isPrime === 0 && i >= 2) // remove not prime numbers
    .map(({ i }) => i) // output only the values
}

eratosthenes(1000000)返回包含78498素数的数组。

赞(0）分享  回复(0）举报  2023-03-21
rvpgvaaj

rvpgvaaj7#

function get_primes_of(n)
{
    let primes = [];
    for (i = 0; i <= n; i++)
    {
        primes[i] = 1;
    }
    primes[0] = primes[1] = 0;
    for (i = 2; i <= n; i++)
    {
        if (primes[i] == 1)
        {
            for (j = 2; i * j <= n; j++)
            {
                primes[j] = 0;
            }
        }
    }
    return primes;
}
赞(0）分享  回复(0）举报  2023-03-21
3b6akqbq

3b6akqbq8#

正如Wikipedia上解释的那样，Eratosthenes的Sieve很容易在JavaScript中实现。只需使用现代ES，不需要到处使用这些for循环。
1.准备从2到max的数字列表
1.抢第一，是质数
1.所以把它推到质数
1.并移除多路复用
1.重复剩下的，如果有意义
1.合并剩下的，它们也是质数

/* ----------------- algorithm itself ---------------- */

const useSieve = m => {
  const primes = []
  let n = Array.from({length: --m}, (_, i) => i + 2) // 1

  do {
    const p = n.shift()                              // 2
    primes.push(p)                                   // 3
    n = n.filter(c => c % p)                         // 4
  } while (n[0] < m / n[0])                          // 5

  return primes.concat(n)                            // 6
}


/* ----------- test for primes to 1 000 000 ---------- */

const start = performance.now()
const primes = useSieve(1_000_000)
const duration = performance.now() - start

console.log(
  `Found ${primes.length} primes in ${duration / 1000} s`
)
赞(0）分享  回复(0）举报  2023-03-21
ztyzrc3y

ztyzrc3y9#

有代码：

function eratoSthenes(n){
    let isPrime = new Array(n + 1);
    isPrime.fill(true);

    isPrime[0] = false;
    isPrime[1] = false;

    for(let i= 2;i * i <= n;i++){
        for(let j = 2 * i;j <=n; j += i){
            isPrime[j] = true
        }
    };

    return isPrime
};
赞(0）分享  回复(0）举报  2023-03-21
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备2022004421号-2 NULL123 https://www.null123.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com