C-Eratosthenes筛-BitField

我将要实现Sieve of Eratosthenes，并且对筛板有一个一般性的问题。

我现在已经在C中实现了很多次筛子，并且始终使用uint8_t数组(<stdint.h>之外)作为筛子。这是相当低的内存效率，因为即使要使用一位，每个数字也会使用8位进行筛选。

我将如何在C语言中进行此操作？我需要一个位数组。我几乎可以创建任何类型的数组(uint8_t，uint16_t，uint32_t，uint64_t)并使用位掩码访问单个位，等等。

我应该选择哪种数据类型，以及在不损失性能的情况下应该使用哪些操作来访问这些位？

PS:我不认为这是BitArray实现的重复，因为它的问题是关于Eratosthenes筛的特定问题，因为它的主要性质需要有效(不仅在内存使用方面，而且在访问方面)。我当时在想，也许可以使用不同的技巧来提高筛分过程的效率。

最佳答案

正如Weather Vane在他的评论中提到的那样，您可以仅考虑其他所有数字来节省额外的空间，因为除2以外的所有偶数都是非质数。

因此，在您的位数组中，每个位代表一个奇数。

这是我几年前使用此技术所做的一种实现。

#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <time.h>
#include <math.h>
#include <stdint.h>

uint8_t *num;
int count = 0;
FILE *primefile;

int main(int argc, char *argv[])
{
  int i,j,root;
  time_t t;

  if (argc>1) count=atoi(argv[1]);
  if (count < 100) {
    fprintf(stderr,"Invalid number\n");
    exit(1);
  }
  if ((num=calloc(count/16,1))==NULL) {
    perror("calloc failed");
    exit(1);
  }
  if ((primefile=fopen("primes.dat","w"))==NULL) {
    perror("Coundn't open primes.dat");
    exit(1);
  }
  t=time(NULL);
  printf("Start:\t%s",ctime(&t));
  root=floor(sqrt(count));
  // write 2 to the output file
  i=2;
  if (fwrite(&i,sizeof(i),1,primefile)==0) {
    perror("Couldn't write to primes.dat");
  }
  // process larger numbers
  for (i=3;i<count;i+=2) {
    if ((num[i>>4] & (1<<((i>>1)&7)))!=0) continue;
    if (fwrite(&i,sizeof(i),1,primefile)==0) {
      perror("Couldn't write to primes.dat");
    }
    if (i<root) {
      for (j=3*i;j<count;j+=2*i) {
        num[j>>4]|=(1<<((j>>1)&7));
      }
    }
  }
  t=time(NULL);
  printf("End:\t%s",ctime(&t));
  fclose(primefile);
  return 0;
}

在这里，num是根据搜索上限动态分配的位数组。因此，如果您要查找所有最大为10亿(10亿)个质数的内存，它将使用64000000(6400万)个字节的内存。

关键表达式如下:

对于“普通”位数组:

设置位i:

num[i>>3] |= (1<<(i&7);
// same as num[i/8] |= (1<<((i%8));

检查位i:

(num[i>>3] & (1<<(i&7))) != 0
// same as (num[i/8] & (1<<(i%8))) != 0

由于我们只跟踪其他所有数字，因此我们将i除以2(或等效地，右移1:

num[i>>4] |= (1<<((i>>1)&7);
// same as num[(i/2)/8] |= (1<<(((i/2)%8));

(num[i>>4] & (1<<((i>>1)&7))) != 0
// same as (num[(i/2)/8] & (1<<((i/2)%8))) != 0

在上面的代码中，有一些微优化，其中除法和模数除以2的幂被位移和逐位与掩码所代替，但是大多数编译器都应该为您完成。

关于C-Eratosthenes筛-BitField，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/38060210/