sieve using a bit array

My previous post had the array starting at MSB. i.e.

[3,5,7,11,13,17,19,23,29,31] turned into

0111 0110 1101 0011
rather than
1100 1011 0110 1110

That was mainly due to me using Python's BitVector to create the array, and then reading it left to right. It made sense at the time!

The latter makes more sense with regards to "getting the nth bit".

Anyway, here's a prime sieve that uses a bit array for storage, and only keeps information for odds.

#define UNSET_BIT(i,n)  i[(n) / 32] &= ~(1 << (n) % 32)
#define GET_BIT(i,n)    ((i[(n) / 32] & 1 << (n) % 32) != 0)

void get_primes_bv_odds(unsigned int n) {
    unsigned int *sieve;
    unsigned int i, j;

    sieve = malloc(sizeof(unsigned int) * ((n + 63) / 64));
    assert(sieve);

    for (i = 0; i < (n + 63) / 64; i++) sieve[i] = 0xffffffff;
    UNSET_BIT(sieve, 0);        /* 1 isn't prime */
    for (i = 3; i < sqrt(n); i += 2) {
        if (GET_BIT(sieve, i / 2) == 0) continue;
        for (j = i * i; j < n; j += i * 2) UNSET_BIT(sieve, j / 2);
    }

    printf("2\n");
    for (i = 1; i < n; i += 2) if (GET_BIT(sieve, i / 2)) printf("%d\n", i);
}