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?
