Sito Eratostenesa w C

Question

Witam, dostałem na studiach takie zadanie:

Zaimplementuj algorytm sita eratostenesa do obliczania kolejnych liczb pierwszych. W implementacji sita zapisz informacje o każdej liczbie (czy jest pierwsza czy nie) na jednym bicie(skorzystaj z operacji bitowych)

O ile sama implementacja sita nie stanowi dla mnie problemu to niejasne jest dla mnie drugie zdanie(zapisz informacje o każdej liczbie na jednym bicie). Czy mógłby ktoś mnie naprowadzić o co w tym zdaniu chodzi i jak sie do tego zadania zabrać ? Z góry dzięki.

 

Comments

Sito Eratostenesa wymaga tablicy true-false na każdą badaną liczbę. Kiedyś gdy implementowałem taki algorytm w pascalu (na Odrze 1305) użyłem konstrukcji:

packed array [2..10000000] of boolean;

Nie zmieściłoby to się w 1MB pamięci tej maszyny gdyby każdy element tablicy zajmował cały jeden bajt. Na szczęście słówko packed oznaczało, że kompilator ma to upchać jak się da i w jednym bajcie znalazło się 8 elementów (po 1 bicie). Choć pewnie było to po 24 elementy w słowie (Odra miała 24 bitowe słowo). Dzięki temu 128kB pamięci i 15 minut pracy wystarczyło.

Masz zaimplemetować upchaną tablice operacjami bitowymi - do tego służą operatory &, | i ^. Działają one w ten sposób, że argumenty są traktowane jako ciąg bitów (8, 16, 32 lub 64 bitów) i oblicz się odpowiednio iloczum logiczny, sumę logiczną lub xor w trybie bit w bit. Do twoich celów będziesz musiał stosować tzw maski - czyli takie liczby w których tylko jeden bit jest 1 a reszta zerem (lub odwrotnie). Wykorzystując takie maski możesz operować na pojedynczych bitach liczby.

sprawdzenie bitu:     wartość & maska

ustawienie bitu:  wartość |= maska

skasowanie bitu:   wartość &= ~maska

Oczywiście będzie trzeba rozbić wartość liczby (indeksu) na część adresującą bajty lub słowa i część indeksującą bit w słowie.

 

---

@yachikson,  @Oscar bardzo ładnie rozpisał, ja tylko dopowiem, że żeby stworzyć maskę z 1 na i-tym bicie i 0 na pozostałych używa się operatora << ( 1 << i ). Np. 1 << 5 to 00100000.

Answer 1

Masz od tego std::bitset. Posiada operatory bitowe, przesunięć... https://en.cppreference.com/w/cpp/utility/bitset