写了个打印质数的小程序

如果需要打印1亿以下的质数的话,那么这个程序的计算是很快的,10秒左右。10亿就慢很多了。如果再往上,那么就会因为存储的问题而溢出了(内存不够以及int的上限是21亿)。
如何改进这个程序让它的内存占有率在一个合理的范围内(而不是随着n线形增长)。
另外,这段程序需要大量的IO写操作。貌似应该赶紧把printf替换成fwrite。另外,要不要用write自己来管理缓存,或者用mmap?

#include <iostream>

#include <stdlib.h>
#include <locale.h>
#include <sstream>

static void usage(){
  printf("usage:%s <num>\n",getprogname());
}

static inline int nextPrime(int s[],size_t slen,uint8_t* mask,size_t maskLen,int max){
  return 0;
}

static int comp(const void* left,const void* right){
  return *(uint8_t*)left-*(uint8_t*)right;
}

static const uint8_t checkPoint[]={1,7,11,13,17,19,23,29};

static void setbitmask(int pv,uint8_t* mask,int num,int per){
  int base=pv/per;
  int v;
  if(pv<per) v=per+pv-per%pv;
  else v=pv;
  for(;v<num;v+=pv){
    uint8_t q=(uint8_t)(v%per);
    //0<=q<=per
    uint8_t* found=(uint8_t*)bsearch(&q,checkPoint,sizeof(checkPoint)/sizeof(checkPoint[0]),
                                    sizeof(checkPoint[0]),comp);
    if(found){
      mask[v/per-1]|=1<<(found-checkPoint);
    }
  }

}

static void printPrimes(int num){
  const int smallPrimes[]={3,5,7,11,13,17,19,23,29};

  const int per=30;
  const int n=num/per;
  uint8_t* const mask=(uint8_t*)calloc(n,1);
  const int *end=smallPrimes+sizeof(smallPrimes)/sizeof(smallPrimes[0]);
  for(const int* p=smallPrimes;p!=end;++p){
    //base=mi*per;
    setbitmask(*p,mask,num,per);
  }
  for(int i=0;i!=n;++i){
    uint8_t v=mask[i];
    for(int j=0;j!=8;++j){
      if(!(v & (1<<j))) {
       // this is a prime
       int result;
       if( (result=(i+1)*per+checkPoint[j])<=num) {
         printf("%d\n",result);
         setbitmask(result,mask,num,per);
       }
      }
    }
  }

  free(mask);
}

int main(int argc,char* argv[]){
  setlocale(LC_ALL,"");
  if(argc<2 ){
    usage();
    return 0;
  }

  std::stringstream ss;
  ss<<argv[1];
  int num;
  ss>>num;

  printPrimes(num);
  return 0;
}

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥