Skip to content

Instantly share code, notes, and snippets.

@henkman

henkman/eratosthenes.c

Created February 28, 2023 17:29
Show Gist options
  • Save henkman/a25e0b8e78fafc53d5d01ff76b06240f to your computer and use it in GitHub Desktop.
Save henkman/a25e0b8e78fafc53d5d01ff76b06240f to your computer and use it in GitHub Desktop.
Download ZIP
Raw
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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment