#include <stdlib.h>
#include <stdio.h>

int get_bit(unsigned char *v, int offset)
{
        offset--;
        int a = offset / 8;
        int b = offset % 8;
        return v[a] & (1 << b) ? 1 : 0;
}

void set_bit(unsigned char *v, int offset)
{
        offset--;
        int a = offset / 8;
        int b = offset % 8;
        v[a] |= 1 << b;
}

void sieve_of_eratosthenes(unsigned char *numbers, unsigned char *primes, int N)
{
        set_bit(numbers,1);
        for (int k=2;k<=N;k++) {
                if (!get_bit(numbers,k)) {
                        set_bit(primes,k);
                        set_bit(numbers,k);
                        for (int l=k+1;l<=N;l++) {
                                if (get_bit(numbers, l)) continue;
                                if (l % k == 0) {
                                        set_bit(numbers,l);
                                }
                        }
                }
        }
}


int main()
{
        unsigned char *numbers = (unsigned char*) calloc(10000000/8+1,1);
        unsigned char *primes = (unsigned char*) calloc(10000000/8+1,1);

        sieve_of_eratosthenes(numbers,primes,100);

        for (int k=0;k<100;k++) {
                if (get_bit(primes,k)) {
                        printf("%10d is a prime\n", k);
                }
        }

        return 0;
}