使用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)改为分配堆内存.这将使你超过〜1Mil的数组元素.

free如果你不再使用它,请记住记忆.如果冯不知道的malloc或免费的,阅读的功能,通过提供的联机帮助页(手册)man 3 malloc和man 3 free任何Linux终端上.(或者你可以只是谷歌man malloc)

编辑:使其calloc(1000000, sizeof(long int))具有0初始化数组,这可能更好.

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

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

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

假设您从0开始计数.

这使得你在uint32_t位掩码数组上的set操作得到一个数字n:

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

为32位类型节省了大约99%的内存.玩得开心:D

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

但是,我已经用大约15行代码(也用于projecteuler)写了一个用于2和3的C和2轮的因子分解,因此可以有效地实现这些东西;)