javascript - 如何使用 JSFiddle 在浏览器中计算所有具有很大最大值的素数

Question

我正在研究 JS 的一些典型类型，我遇到了一个需要一个非常大的数字的所有素数的类型。我尝试了following in JSFiddle 。

findPrimes(max){
   let dont = [], primes = [];
   for (var i = 2; i <= max; i++) {
     if (!dont[i]) {
       primes.push(i);
       for (var j = i; j <= max; j += i) dont[j] = true;
     }
   }
}

这在 this.findPrimes(51475143); 之前效果相对较好，但是，如果我尝试说... this.findPrimes(851475143); 我得到一个JS 引擎似乎崩溃了，表情悲伤。我知道我可能可以直接使用 V8 并挤出一点，甚至可能转向基于 C 的节点模块，但为了简单起见，如果可能的话，我想将其保留在浏览器中。如果没有并且可以提供证据，我会接受该答案。

Answer 1

您遇到的问题可能是由于内存不足所致，您的 dont数组是罪魁祸首。幸运的是，由于它只是一个 bool 数组，因此您可以使用位数组执行相同的操作，这将节省一些空间。

JavaScript 没有任何 native 位数组类型，但您可以通过存储 32 位数字的数组并使用按位运算符来检索或设置所需的位来模拟一种类型。所以类似:

class BitArray {
  constructor(len) {
    this.arr = Array(Math.ceil(len / 32)).fill(0)
  }

  set(i) {
    const j = Math.floor(i / 32)
    this.arr[j] = this.arr[j] | (1 << (i % 32))
  }

  get(i) {
    const j = Math.floor(i / 32)
    return (this.arr[j] & (1 << (i % 32))) && 1 || 0;
  }
}

然后，仅此而已，您就可以运行代码片段并获得结果(尽管需要一段时间):

class BitArray {
  constructor(len) {
    this.arr = Array(Math.ceil(len / 32)).fill(0)
  }

  set(i) {
    const j = Math.floor(i / 32)
    this.arr[j] = this.arr[j] | (1 << (i % 32))
  }

  get(i) {
    const j = Math.floor(i / 32)
    return (this.arr[j] & (1 << (i % 32))) && 1 || 0;
  }
}

function findPrimes(max) {
  const dont = new BitArray(max)
  const primes = [];
  for (var i = 2; i <= max; i++) {
    if (!dont.get(i)) {
      primes.push(i);
      for (var j = i * 2; j <= max; j += i) dont.set(j);
    }
  }

  return primes;
}

const primes = findPrimes(851475143);
console.log("Done. Max Prime:", primes[primes.length - 1])
console.log("And last 10 primes:", primes.slice(-10))

但是，除此之外，您还可以对筛选器进行更多优化:

• 您可以开始j在i*i而不仅仅是i ，因为任何小于该数的素数都小于 i已经作为一个因素(因此，已经在 dont 中设置)。
• 您实际上只需要检查奇数作为筛子的一部分，因此您可以将外部循环更改为每次递增 2( i += 2 而不是 i++ )，然后将内部循环更改为每次递增i*2而不是i (因为 j + i*(odd) 始终是偶数)。

使用这些，您可以将代码片段更改为:

class BitArray {
  constructor(len) {
    this.arr = Array(Math.ceil(len / 32)).fill(0)
  }

  set(i) {
    const j = Math.floor(i / 32)
    this.arr[j] = this.arr[j] | (1 << (i % 32))
  }

  get(i) {
    const j = Math.floor(i / 32)
    return (this.arr[j] & (1 << (i % 32))) && 1 || 0;
  }
}

function findPrimes(max) {
  const dont = new BitArray(max / 2)  // Only need half the memory, since we only check odds.
  const primes = [2];                 // We already know 2 is prime
  for (var i = 3; i <= max; i += 2) { // Start at 3, increment by 2, so only odds are checked.
    if (!dont.get((i-1)/2)) {         // The (i-1)/2 converts each odd to it's "halfway" number
      primes.push(i);
      for (var j = i*i; j <= max; j += i*2) dont.set((j-1)/2);
    }
  }

  return primes;
}

const primes = findPrimes(851475143);
console.log("Done. Max Prime:", primes[primes.length - 1])
console.log("And last 10 primes:", primes.slice(-10))

正如您所看到的，对于最后 10 个素数，您得到了相同的结果，并且至少从传闻来看，它似乎运行得更快一些。