Sito eratostenesa

Question

Witam, chcę napisać program obrazujący właśnie działanie sita eratostenesa, ale nie wiem czy ja w ogóle dobrze nad tym myślę :

#include <iostream>
#include <cmath>
using namespace std;
 
int main()
{
 int TAB[101];
 for (int i=2; i<101;i++){ TAB[i]=1;
    //for (int k=4; k<101;k+=2) TAB[k]=0; } tu wywaliłam wielokrotności dwójki
    for (int s=i+1; s<101; s=s+1+i) TAB[s]=0;} // tu próbowałam jakby uogólnić ten wzór wyrzucania cyferek ale coś nie wypaliło :/
 
 
 
 
  for (int l=2; l<101;l++)  cout<<TAB[l];
 
    return 0;
}

Czy ja w ogóle dobrze nad tym myślę?
(wiem w internecie jest dużo kodów ilustrujących działanie tego sita, tylko, że jestem na takim etapie nauki, że większości wielu funkcji których się tam używa ja po prostu nie rozumiem)

 

Answer 1

Po pierwsze staraj sie pisać czytelny kod źródłowy... Chociażby ten zamieszczony niżej jest dużo bardziej czytelny.

 int TAB[101];
 for (int i=2; i < 101 ; i++) {
     TAB[i]=1;
    for (int s=i+1; s<101; s=s+1+i) {
        TAB[s]=0;
    }
 }

Po drugie gdyby wziąć pseudokod z wikipedii:

To widać po pierwsze że nie inicializujesz tablicy nigdzie na 'true'. Po drugie nie wiem po co jest TAB[i]=1; w ósmej linij twojego kodu. Po trzecie nie sprawdzasz czy aktualna sprawdzana jest pierwsza tylko od razu lecisz z zagnieżdżoną pętlą. Po czwarte dlaczego w zagnieżdżonej pętli wszędzie masz i+1 zamiast i ?

Odnośnie:

... których się tam używa ja po prostu nie rozumiem

Co za problem użyć dokumentacji aby douczyć się brakujących rzeczy ?

 

Ciężko napisać sito prościej niż to:

#include <iostream>

int main()
{
    int tab[101];
    for(int i = 0; i < 101; ++i) {
        tab[i] = 1;
    }
    
    for(int i = 2; i < 101; ++i) {
        if(tab[i] == 1) {
            for(int j = 2*i; j < 101; j += i) {
                tab[j] = 0;
            }
        }
    }
    
    for(int i = 2; i < 101; ++i) {
        if(tab[i] == 1) {
            std::cout << i << " ";
        }
    }
    
    std::cout << std::endl;
    return 0;
}

Mam nadzieję że uda Ci się przeanalizować ten kod.

Comments

Dziękuję, postaram się :)