eratosthenes.c

typedef struct {
  unsigned char *mem;
  size_t bytes;
} BS;

static void BSInit(BS *bs, size_t bits) {
  size_t bytes = bits / 8;
  if (bits % 8)
    bytes++;
  bs->bytes = bytes;
  bs->mem = malloc(sizeof(unsigned char) * bytes);
}

static void BSFree(BS *bs) { free(bs->mem); }

static void BSSetAll(BS *bs, bool set) {
  memset(bs->mem, set ? 0xFF : 0, sizeof(unsigned char) * bs->bytes);
}

static bool BSGet(BS *bs, size_t bit) {
  return (bs->mem[bit / 8] & (1 << (bit % 8))) != 0;
}

static void BSSet(BS *bs, size_t bit) { bs->mem[bit / 8] |= (1 << (bit % 8)); }

static void BSUnset(BS *bs, size_t bit) {
  bs->mem[bit / 8] &= ~(1 << (bit % 8));
}

static void sieve(BS *bs, size_t n) {
  BSSetAll(bs, true);
  for (size_t i = 4; i <= n; i += 2)
    BSUnset(bs, i);
  size_t m = sqrt(n);
  for (size_t i = 3; i <= m; i += 2)
    for (size_t e = i + i; e <= n; e += i)
      BSUnset(bs, e);
}