После поиска в сети я узнал, что побитовая версия сита из эратосфена довольно эффективна. Проблема в том, что я не могу понять математику / метод, который он использует.

Версия, которой я был занят, выглядит следующим образом:

#define MAX 100000000
#define LIM 10000

unsigned flag[MAX>>6]={0};

#define ifc(n) (flag[n>>6]&(1<<((n>>1)&31)))         //LINE 1
#define isc(n) (flag[n>>6]|=(1<<((n>>1)&31)))        //LINE 2

void sieve() {
    unsigned i, j, k;
    for(i=3; i<LIM; i+=2)
        if(!ifc(i))
            for(j=i*i, k=i<<1; j<LIM*LIM; j+=k)
                isc(j);
}

Пункты, которые я понял (пожалуйста, поправьте меня, если я ошибаюсь):

Оператор в строке 1 проверяет, является ли число составным.Оператор в строке 2 помечает число «n» как составное.Программа хранит значение 0 или 1 с битом типа int. Это имеет тенденцию уменьшать использование памяти до x / 32. (x - это размер, который был бы использован, если бы int использовался для хранения 0 или 1, а не как в моем решении выше)

Точки, которые идут сейчас над моей головой:

Как работает функция в LINE 1? Как функция проверяет, является ли число составным или нет.Как функция в LINE 2 устанавливает бит.Я также узнал, что побитовое сито также эффективно по времени. Это из-за использования только побитовых операторов или что-то еще способствует этому.

Есть идеи или предложения?