Eratosthenes

eratosthenes_prime.c

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

#define MAX 10000000

void bit_true(char* vec, int pos) {
    int char_idx = pos / 8;
    int bit_idx = pos % 8;
    int mask = 1 << bit_idx;
    vec[char_idx] = vec[char_idx] | mask;
}

void bit_false(char* vec, int pos) {
    int char_idx = pos / 8;
    int bit_idx = pos % 8;
    int mask = 255;
    int imask = 1 << bit_idx;
    mask = mask ^ imask;
    vec[char_idx] = vec[char_idx] & imask;
}

int bit_get(char* vec, int pos) {
    int char_idx = pos / 8;
    int bit_idx = pos % 8;
    int mask = 1 << bit_idx;
    return (0 < (vec[char_idx] & mask));
}

mul_n_bit_on(char* vec, int n) {
    int i;
    for (i = n*2; i <= MAX; i += n) {
        bit_true(vec, i);
    }
}

int main(int argc, char** argv) {
    int i;
    char* vec = (char*)malloc(sizeof(char) * (MAX/8 + 1));

    mul_n_bit_on(vec, 2);
    for (i = 3; i <= MAX; i+=2) {
        if (!bit_get(vec, i)) {
            mul_n_bit_on(vec, i);
        }
    }

    // list up
    /*
    for (i = 1; i <= MAX; i++) {
        if (!bit_get(vec, i)) {
            printf("%d\n", i);
        }
    }*/


	free(vec);
}