c - 在 C 中使用筛法列出最多 20 亿的素数

Question

我尝试使用 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;
}

Answer 1

long int mark[1000000] 进行堆栈分配，这不是您想要的内存量。尝试使用 long int *mark = malloc(sizeof(long int) * 1000000) 来分配堆内存。这将使您超过 ~100 万个数组元素。

如果您不再使用内存，请记住释放内存。如果您不知道 malloc 或 free，请阅读功能的联机帮助页(手册)，可在任何 linux 终端上通过 man 3 malloc 和 man 3 free 获得。 (或者你可以谷歌 man malloc)

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

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

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

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 行代码(也适用于 projecteuler)用 C 语言为 2 和 3 编写了一个 primesieve wich wheel factorization，因此可以有效地实现这些东西；)