Skip to content

Instantly share code, notes, and snippets.

@antonmedv
Created September 15, 2017 07:29
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save antonmedv/a433a2ca0e211189342edb9542a5f179 to your computer and use it in GitHub Desktop.
Save antonmedv/a433a2ca0e211189342edb9542a5f179 to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes (bit array optimized)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LIMIT 23e9
typedef unsigned char word_t;
int check(word_t *primes, uint64_t i)
{
word_t r = i % 8;
uint64_t n = i / 8;
return (primes[n] >> r) & 1;
}
void clear(word_t *primes, uint64_t i)
{
word_t r = i % 8;
uint64_t n = i / 8;
primes[n] &= ~(1 << r);
}
int main()
{
word_t *primes;
uint64_t i, j, length;
length = LIMIT / 8 + 1;
primes = malloc(length);
memset(primes, 255, length);
for (i = 2; i < LIMIT; i++)
if (check(primes, i))
for (j = i; i * j < LIMIT; j++)
clear(primes, i * j);
for (i = 2; i < LIMIT; i++)
if (check(primes, i))
printf("%llu\n", i);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment