Sito Eratostenesa na liczbach nieparzystych

Question

Mam za zadanie napisać program, który wśród liczb z przedziału <2; 200) znajdzie liczby pierwsze korzystając z sita Eratostenesa. Tablica logiczna przechowuje informacje o pierwszości liczb nieparzystych, gdzie indeks d tablicy przyporządkowany jest liczbie 2*d+1. Zatem program korzysta z tablicy 100-elementowej (gdzie ostatnia szufladka 99 odpowiada liczbie 99*2+1=199).

Idąc tym tokiem program ma przyporządkować fałsz takim szufladkom tabeli, które przyporządkowano liczbom będącym wielokrotnościami innych liczb nieparzystych. Program najpierw sprawdza nieparzyste wielokrotności liczby 3 (d=1 odpowiada 2*1+1=3) - 3*3, 3*5, 3*7 aż do 3*65=195, i przyporządkowuje odpowiednim szufladkom fałsz, potem wielokrotności 5, itd. aż do 13, czyli d = 6 (na 15 pętla powinna się już zakończyć, bo 15*15>200). Wtedy w pętli do...while sprawdzane będą kolejne liczby nieparzyste, z pominięciem tych, które są złożone. Siedzę już nad tym od dłuższego czasu i nie wiem, jak odpowiednio dobrać warunki, aby program mógł wskazać wszystkie liczby pierwsze z wskazanego przedziału. Poniżej zamieszczam to co udało mi się napisać. N to liczba szufladek tablicy, równa 100.

void SitoEratostenesa(bool Pierwsze[])
{
    int d = 1;
    Pierwsze[N] = true;
    while((2*d+1)*(2*d+1)<2*N)
    {
        for(int i = 2*d+1; (i*(2*d+1)-1)/2 < N; i+=2)
        {
            Pierwsze[(i*(2*d+1)-1)/2] = false;
        }
        do
            d++;
        while(!Pierwsze[d]);
    }
}

Kiedy spróbuję wypisać liczby z pętli:

for(int i = 1; i < N; i++)
    {
        if(Pierwsze[i]) cout << 2*i + 1 << endl;
    }

to na ekranie nie pojawią się wszystkie liczby pierwsze z przedziału, pojawią się tylko (pomijam 2):

3
5
17
19
23
67
149
161
193
197

Co należałoby pozamieniać, aby procedura działała tak jak należy? 

Comments

W linii 4 nie wychodzisz przypadkiem poza tablicę? I jaki sens miałaby ta instrukcja?

Czyżby to miała być inicjalizacja tablicy?

---

Tak, chciałem być hop do przodu i tak nadać każdej szufladce wartość true. Rozwiązałem to już za pomocą pętli i działa, dzięki :) Jednak gdybym chciał zainicjować tablicę poza procedurą (czyli bool Pierwsze[N] = {true}, jeśli dobrze myślę) z pominięciem wspomnianej pętli, to nic się wtedy nie wyświetli. Umiałbyś wyjaśnić, dlaczego tak się dzieje?

---

Taka inicjalizacja za pomocą nawiasów { } w C jest możliwa tylko przy deklaracji zmiennej i nie działa przy instrukcjach. Zawartość jest interpretowana tak, że co zostało napisane zostanie tak wypełnione, ale cała reszta zostanie wyzerowana, a 0 to false. Czyli wypełniasz zerowy element wartością true, a resztę false. Wypełnienie tablicy wartością false to oznaczenie wszystkich liczb jako nie-pierwszych i już algorytm tego nie ruszy.

Nie wiem, czy nowsze wersje C++ czegoś tutaj nie dodały.