0

我想通过筛选多达 100,000,000 个来生成素数，但是声明这个范围的 bool 数组会使我的程序崩溃。这是我的代码：

long long i,j,n;
bool prime[100000000+1];
prime[1]=prime[0]=false;
for(i=2;i<=100000000;i++){
    prime[i]=true;
}
for(i=2;i<=100000000;i++){
    if(prime[i]==false){
        continue;
    }
    for(j=i*2;j<=100000000;j+=i){
        prime[j]=false;
    }
}

我怎么解决这个问题？

4

3 回答 3

3

数组素数的大小为 100 MB，不允许在堆栈上声明如此大的数组。尝试将数组放在全局范围内以在堆上分配它，或者使用 new(in C++) 或 malloc(in C) 分配它。之后不要忘记释放内存！

于 2013-03-25T15:54:57.073 回答
2

变量可以存储在三个不同的内存区域：静态内存、自动内存、动态内存。自动内存（非静态局部变量）的大小有限，你越过了它，这会使程序崩溃。另一种方法是将您的数组标记为静态，这会将您的数组放置在静态存储中，或者使用动态内存。

由于这被标记为 C++... 使用std::vector简单易用并使用动态内存。

#include <vector>
//...
//...
long long i,j,n;
std::vector<bool> prime(100000000+1, true);
prime[1]=prime[0]=false;
for(i=2;i<=100000000;i++){
    if(prime[i]==false){
        continue;
    }
    for(j=i*2;j<=100000000;j+=i){
        prime[j]=false;
    }
}

std::vector<bool>使用“位效率”表示，这意味着这里的 std::vector 将比传统数组少占用大约 8 1倍的内存。

std::bitset类似，但大小是恒定的，您必须将其标记为静态以避免占用自动内存中的空间。

您还没有问过，但 Erastostenes Sieve 并不是计算大量素数的最快算法。似乎阿特金筛子更快，使用更少的内存。

1 - 当您的系统有 8 位字节时。

于 2013-03-25T16:19:13.100 回答
1

你不应该做一个这样大小的整体筛子。相反，使用 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

您可以在我的博客上看到更多涉及素数的算法。

于 2013-03-25T16:36:39.550 回答