3

我尝试使用 Sieve Eratosthenes 方法列出最多 20 亿个素数。这是我用的！

我面临的问题是，我无法超过 1000 万个数字。当我尝试时，它显示“分段错误”。我在网上找了找原因。有些网站说，这是编译器本身的内存分配限制。有人说，这是硬件限制。我正在使用安装了 4GB RAM 的 64 位处理器。请建议我列出它们的方法。 

#include <stdio.h>
#include <stdlib.h>

#define MAX 1000000
long int mark[MAX] = {0};

int isone(){
   long int i;
   long int cnt = 0;
   for(i = 0; i < MAX ; i++){
      if(mark[i] == 1)
         cnt++;
   }
   if(cnt == MAX)
      return 1;
   else
      return 0;
}



int main(int argc,char* argv[]){
   long int list[MAX];
   long int s = 2;
   long int i;
   for(i = 0 ; i < MAX ; i++){
      list[i] = s;
      s++;
   }
   s = 2;
   printf("\n");

   while(isone() == 0){
      for(i = 0 ; i < MAX ; i++){
         if((list[i] % s) == 0)
            mark[i] = 1;
      }
      printf(" %lu ",s);
      while(mark[++s - 2] != 0);
   }

   return 1;
}
4

2 回答 2

6

long int mark[1000000]做堆栈分配，这不是你想要的内存量。尝试long int *mark = malloc(sizeof(long int) * 1000000)分配堆内存。这将使您超过约 1 百万个数组元素。

记住free记忆，如果你不再使用它。如果您不知道 malloc 或 free，请阅读功能的手册页（手册），可通过任何 linux 终端man 3 malloc或man 3 free在任何 linux 终端上使用。（或者你可以只是谷歌man malloc）

编辑：让它calloc(1000000, sizeof(long int))有一个初始化为 0 的数组，这可能更好。

此外，您可以将数组的每个元素用作位掩码，以便能够为每位存储一个标记，而不是每个 sizeof(long int) 字节。我建议使用固定宽度的整数类型，例如uint32_t数组元素，然后将数组的第 ' 个元素中的第(n % 32)' 位设置(n / 32)为 1，而不是仅将第 n 个元素设置为 1。

您可以使用以下方法设置整数的第 n 位i：

uint32_t i = 0;
i |= ((uint32_t) 1) << n

假设您从 0 开始计数。

这使您对数字 n 的 uint32_t 位掩码数组进行设置操作：

mask[n / 32] |= ((uint32_t)1) << (n % 32)

为 32 位类型节省了 99% 以上的内存。玩得开心 :D

此处使用的另一种更高级的方法是素数轮因式分解，这基本上意味着您事先将 2,3 和 5（甚至可能更多）声明为素数，并且在掩码数组中仅使用不能被其中一个整除的数字. 但这是一个非常先进的概念。

但是，我用大约 15 行代码（也用于投影仪）用 C 语言编写了 2 和 3 的轮因式分解的素数筛，因此可以有效地实现这些东西；）

于 2013-01-08T09:21:59.023 回答
2

最直接的改进是切换到表示奇数的位。因此，要覆盖M=20 亿个数字或 10 亿个几率，您需要 1000/8 = 1.25 亿字节 =~ 120 MB 内存（仍然使用calloc函数在堆上分配它们）。

位置上的位i将代表数字2*i+1。因此，当标记一个素数的倍数时p，即p^2, p^2+2p, ..., M，我们p^2=(2i+1)^2=4i^2+4i+1在位置上用一个位表示j=(p^2-1)/2=2i(i+1)，并且在它上面的下一个倍数p在位置增量处p=2i+1，

for( i=1; ; ++i )
  if( bit_not_set(i) )
  {
      p=i+i+1;
      k=(p-1)*(i+1);
      if( k > 1000000000) break;
      for( ; k<1000000000; k+=p)
         set_bit(k); // mark as composite
  }
// all bits i>0 where bit_not_set(i) holds, 
// represent prime numbers 2i+1

下一步是切换到适合您的缓存大小的较小段中工作。这应该加快速度。您只需要为 20 亿平方根以下的素数（即 44721）保留内存区域。

首先，筛选这个较小的区域以找到那里的素数；然后将这些素数写入一个单独的int数组；然后使用这个素数数组来筛选每个段，可能将找到的素数打印到stdout或其他任何内容。

于 2013-01-08T11:01:47.167 回答