Блог

Я пытаюсь изучить концепцию использования побитового сита Эратосфена. Из того, что я прочитал, я понимаю, что каждый элемент простого массива хранит простое состояние (простое -> 0 или составное -> 1) из 64 чисел. Таким образом, для 64 чисел достаточно всего 1 элемента. Чего я не понимаю, так это того, как это число сопоставляется с этим битом и какова логика, стоящая за этим?

В следующем утверждении: (простое число [x/64] amp; (1 << (( x >> 1) и 31)))

если x равно 5, то 5 >> 1 = 2 (5/2=2) и после по модулю 32 мы получаем 2. Означает ли это, что 2-й бит (из 64 бит) соответствует числу 5? будет ли 2-й бит содержать простой статус числа 5?

Я хочу понять, на каком основании мы получаем 2 (почему мы сдвигаем вправо на 2 бита, а затем по модулю 32) и какова логика этого. Также я запустил программу и попытался отладить, чтобы лучше понять ее, и обнаружил, что элемент в prime array в какой-то момент становится отрицательным. Основной массив имеет тип данных int, поэтому каждый элемент в нем имеет тип int (32 бита). Как int (32-разрядный) может хранить простой статус 64 чисел (64 числа требуют 64 бита для сохранения статуса, я предполагаю)

Было бы полезно, если бы кто-нибудь мог мне помочь! Я просмотрел другие подобные вопросы о переполнении стека, но все еще не мог понять, почему я снова публикую. Пожалуйста, дайте мне знать, как я могу улучшить вопрос, поскольку я новичок в stack overflow.

  
#include <bits/stdc  .h> 
using namespace std; 

 
bool ifnotPrime(int prime[], int x) 
{ 
    
    return (prime[x/64] amp; (1 << ((x >> 1) amp; 31))); 
} 

bool makeComposite(int prime[], int x) 
{ 
    
    prime[x/64] |= (1 << ((x >> 1) amp; 31)); 
} 


void bitWiseSieve(int n) 
{ 
    
    int prime[n/64]; 

    memset(prime, 0, sizeof(prime)); 

     
    for (int i = 3; i * i <= n; i  = 2) { 

        
        if (!ifnotPrime(prime, i)) 
            for (int j = i * i, k = i << 1; j < n; j  = k) 
                makeComposite(prime, j); 
    } 

    
    printf("2 "); 

    for (int i = 3; i <= n; i  = 2) 
        if (!ifnotPrime(prime, i)) 
            printf("%d ", i); 
} 


int main() 
{ 
    int n = 30; 
    bitWiseSieve(n); 
    return 0; 
}