1

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

我试图通过首先创建一个函数来模拟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 的数字，但高于此数字，浏览器似乎会冻结。

是否有某种版本的这种方法可以适应更大的数字，或者我是在叫错树吗？

4

2 回答 2

1

最多 12 位数字是 100,000,000,000。这是很多素数（~ N/log N = 3,948,131,653）。

因此，制作一个高达 10^6 的筛子，将其压缩到约 78,500 个核心素数的数组中，然后使用它们逐段筛选直到您的目标。使用最高为该段当前上限的平方根的素数。通常选择段的大小以使其适合系统缓存。筛选每个片段后，收集其素数。

这被称为埃拉托色尼的分段筛。

于 2013-08-09T20:12:09.183 回答
1

正如@WillNess 建议的那样，您不应该制作一个这种大小的整体筛子。相反，使用 Eratosthenes 的分段筛子在连续的段中执行筛分。在第一段，计算段内每个筛选素数的最小倍数，然后以正常方式将筛选素数的倍数标记为合数；当所有的筛选素数都用完后，该段中剩余的未标记数为素数。然后，对于下一段，每个筛分素数的最小倍数是在前一段中结束筛分的倍数，因此筛分一直持续到完成。

考虑以 20 为一组从 100 到 200 筛分的例子；5个筛选素数是3、5、7、11和13。在从100到120的第一段中，位数组有10个槽，槽0对应101，槽k对应100 + 2*k* + 1， slot 9对应119。segment中3的最小倍数是105，对应slot 2；槽 2+3=5 和 5+3=8 也是 3 的倍数。槽 2 处 5 的最小倍数是 105，槽 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，这是通过正常的 Eratosthenes 筛法计算的。数组qs包含进入筛子的偏移量相应筛选素数的当前段中最小倍数的位数组。在每个段之后，lo前进两倍delta ，因此与筛位数组的索引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尽可能大，只要它适合高速缓存内存，以提高速度。将您的语言库用于位数组，这样您只需为每个筛子位置取一个位。如果你需要一个简单的 Eratosthenes 筛来计算筛分质数，这是我最喜欢的：

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。您可以在我的博客上看到更多涉及素数的算法。

于 2013-08-09T23:36:11.183 回答