javascript - 需要关于如何在 JavaScript 中分解非常大的数字的提示/建议

Question

我的任务是生成一个数组，其中包含最多 12 位数字的所有素数。

我试图模拟 Sieve of Eratosthenes首先创建一个函数 enumerate，它生成一个数组，其中包含从 2 到 num 的每个整数:

var enumerate = function(num) {
    array = [];
    for (var i = 2; i <= num; i++) {
        array.push(i);
    }
    return array;
};

然后我创建了一个函数 leaveOnlyPrimes，它循环遍历并从数组中删除每个数组成员的倍数，最多为 1/2 max(这最终不是每个整数，因为每次迭代数组都会变小):

var leaveOnlyPrimes = function(max,array) {
    for (var i = 0; array[i] <= max/2; i++) {
        (function(mult,array) {
            for (var i = mult*2; i <= array[array.length-1]; i += mult) {
                var index = array.indexOf(i);
                if (index !== -1) {
                    array.splice(index,1);
                }
            }
        })(array[i],array);   
    }
};

这适用于最大约 50000 的数字，但任何高于该值的浏览器似乎都会卡住。

这种方法是否有某种版本可以适应更大的数量，还是我找错了树？

Answer 1

正如@WillNess 建议的那样，您不 应该制作那种尺寸的单个整体式筛子。相反，使用分段式埃拉托色尼筛分连续分段进行筛分。第一段，计算段内各筛质数的最小倍数，然后按照正常方式将筛质数的倍数标为合；当所有的筛选素数都用完后，该段中剩余的未标记数为素数。然后，对于下一段，每个筛分质数的最小倍数是前一段结束筛分的倍数，如此继续筛分直到结束。

考虑以 20 为单位从 100 筛选到 200 的示例； 5个筛选素数分别为3、5、7、11、13。第一段100到120位数组有10个槽位，槽位0对应101，槽位k对应100 + 2*k* + 1，slot 9对应119。段中3的最小倍数为105，对应slot 2； slot 2+3=5 and 5+3=8 也是3的倍数，5的最小倍数在slot 2是105，slot 2+5=7也是5的倍数，7的最小倍数是105在槽2，槽2+7=9也是7的倍数，以此类推。

函数 primes 接受参数 lo、hi 和 delta； lo 和 hi 必须是偶数，lo <hi，lo 必须大于 hi 的平方根。段大小是 delta 的两倍。长度为 m 的数组 ps 包含小于 hi 平方根的筛选素数，由于偶数被忽略，因此删除了 2，由正常的埃拉托色尼筛法。数组 qs 包含相应筛分素数当前段中最小倍数的 sieve 位数组的偏移量。在每个段之后，lo 前进两倍 delta，因此对应于 sieve 位数组的索引 i 的数字是 lo + 2 i + 1。

function primes(lo, hi, delta)
  sieve := makeArray(0..delta-1)
  ps := tail(primes(sqrt(hi)))
  m := length(ps)
  qs := makeArray(0..m-1)
  for i from 0 to m-1
    qs[i] := (-1/2 * (lo + ps[i] + 1)) % ps[i]
  while lo < hi
    for i from 0 to delta-1
      sieve[i] := True
    for i from 0 to m-1
      for j from qs[i] to delta step ps[i]
        sieve[j] := False
      qs[i] := (qs[i] - delta) % ps[i]
    for i from 0 to delta-1
      t := lo + 2*i + 1
      if sieve[i] and t < hi
        output t
    lo := lo + 2*delta

对于上面给出的示例，这称为 primes(100, 200, 10)。在上面给出的示例中，qs 初始为 [2,2,2,10,8]，对应于 105、105、105、121 和 117 的最小倍数，并在第二段重置为[1,2,6,0,11]，对应最小的倍数123、125、133、121、143。

delta 的值很关键；为了速度，您应该使 delta 尽可能大，只要它适合高速缓存。将您的语言库用于位数组，这样您只需为每个筛选位置取一个位。如果您需要一个简单的埃拉托色尼筛法来计算筛素数，这是我最喜欢的:

function primes(n)
  sieve := makeArray(2..n, True)
  for p from 2 to n step 1
    if sieve(p)
      output p
      for i from p * p to n step p
          sieve[i] := False

我会把它留给你翻译成 JavaScript。您可以在 my blog 查看更多涉及素数的算法。 .