Sito Eratostenesa ,C++ .

Question

hej ,ostatnio szukałem w internecie algorytmu Eratostenesa . Ogólnie jego działanie rozumiem , z tym nie mam problemu :) . Ale bardzo zastanawiam się nad pewną kwestią , może zanim przejdę dalej to podam kod :

#include <iostream>

using namespace std;

bool tab[10]; //tablica ,ilosc liczb pierwszych do pomieszczenia (nie rozumiem)

int main()
{
    int n; //zakres
    cin>>n;
    cout<<endl;

    for(int i=2; i*i<=n; i++) //algorytm (rozumiem)
    {
        if(tab[i]==true)
            continue;
        else{
            for(int j=2*i; j<=n; j=j+i)
            {
                tab[j]=true;
            }
        }
    }

    for(int i=2; i<=n; i++) //wypisanie wartoci(rozumiem)
    {
        if(tab[i]==false)
        {
            cout<<i<<"\t";
        }
    }

    return 0;
}

Problem dotyczy tego że w tym przykładzie dałem tylko 10 szufladek w tablicy : bool tab[10];

Więc analogicznie maksymalna wartość n powinna wynosić 9 ( bo tablice liczymy od 0 ) .

Tymczasem program poprawnie wyznacza liczby pierwsze nawet gdy n wynosi 300 !?

Wydaje mi się to nielogiczne bo szufladek jest tylko 10. Wiem że może trudno to pytanie zrozumieć ale sami sobie zobaczcie ... . Dziękuje za wszelką pomoc :)

 

Answer 1

W C++ możesz odczytywać dowolne miejsce w pamięci o np tak:

cout<<dec; // zamiana na liczb na system heksadecymalny
for(int i=0; i<500; i++) cout<<i+1<<" "<<tab[i]<<endl; // bazujac na tablicy

Pokażą się wartości, które są poza rozmiarem tablicy w komórkach pamięci obok. Tak właściwie nie do końca w komórkach pamięci obok, bo przeznaczanie 1 bajta na typ bool to marnotrawstwo miejsca...

W tych komórkach możesz zapisać informacje, ale jest to niebezpieczne. Bo po pierwsze czasami może być w nich jakaś wartość (ale nie musi), a po drugie program może zostać zawieszony za zapisywanie w obszarze pamięci wykorzystywanym przez inny program (albo inaczej mówiąc w obszarze o niedozwolonym dostępie ). 

W tej powyższej pętli możesz zobaczyć jaki nadać n, by program się zawiesił. Wystarczy spojrzeć tam gdzie "komórka" pamięci będzie miała jakąś wartość np u mnie lokalnie:

409 104

Teraz wystarczy podać i+1, czyli u mnie 409. Prawdopodobnie jest ona wykorzystywana przez inny program i w konsoli wyskoczy Ci błąd. Jeżeli nie to wybierz jakąś inną wartość. 

Takie coś jest niebezpieczne więc w kodzie staraj się zawsze takich luk w systemie alokowania pamięci unikać.

Comments

dzięki wielkie za pomoc . Zamiast ustawiać domyślną liczbę elementów w tablicy użyłem dynamicznej alokacji i nie wiem czemu teraz program wysypuje się ,

    int n;
    cin>>n;
    bool *tab;
    *tab = new int[n];

wiem że powód może być prosty ale zawsze miałem problemy ze wskaźnikami

---

Może zamiast new int zrób new bool? :)

---

faktycznie ... dzięki za pomoc

---

Ja też miałem problemy ze wskaźnikami. To prawdziwa zmora dla początkujących już nie mówiąc o dynamicznych dwuwymiarowych tablicach... Pozdrawiam! :)

---

Hej , przepraszam że znowu wracam do tematu mimo iż zamknąłem już pytanie , mianowicie po użyciu dynamicznej alokacji algorytm przestał poprawnie wyznaczać liczby pierwsze :

oto kod :

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin>>n;

    bool *tab = new bool[n+1]; //bo od 0 
    cout<<endl;

    for(int i=2; i*i<=n; i++)
    {
        if(tab[i]==true)
            continue;
        else{
            for(int j=2*i; j<=n; j=j+i)
            {
                tab[j]=true;
            }
        }
    }

    for(int i=2; i<=n; i++)
    {
        if(tab[i]==false)
        {
            cout<<i<<"\t";
        }
    }

    return 0;
}

dość długo zastanawiałem się co może być przyczyną bo bez użycia wskaźnika wszystko działa ok

---

Zauwaz co robi ostatnia petla, sprawdza liczby od 2 do n, a nie wypisuje n liczb pierwszych.

---

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin>>n;

    n = n + 1; // zastosowalem dla pozniejszej wygody i lepszego zrozumienia co sie dzieje

    bool *tab = new bool[n];
    cout<<endl;

    for(int i=2; i*i<=n; i++) // tu bylo tez niedopatrzenie
    {
        if(tab[i] == false) // to z continue bylo chyba bledem
        {
            for(int j=2*i; j<n; j=j+i)
            {
                tab[j]=true;
            }
        }
    }

    for(int i=2; i<n; i++)
    {
        if(tab[i]==false)
        {
            cout<<i<<"\t";
        }
    }

    return 0;
}

 

Wyrzuciłem tego if  z instrukcją continue. W sumie jeszcze nie wiem do końca czemu to robiło błąd... Jeszcze się nad tym zastanowię.

Poza tym zrobiłem warunki trwania pętli od nowa by mieć pewność, że nie miałeś wcześniej drobnych błędów. Okazało się, że oprócz jednego miałeś większość dobrze. Nie pasował o 1 tylko ten warunek matematyczny na zakres, ale on miałby wpływ na jakieś bardzo skrajne sytuacje.

---

teraz działa w porządku ,ale nie mam zielonego pojęcia jaki wpływ ma instrukcja continue na działanie algorytmu...

---

teraz dla oszczędzenia pamięci zacząłem zapisywać dane od tablicy nr 0 :

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin>>n; //n+1 już jest nie potrzebne
    bool *tab = new bool[n];

    cout<<endl;

    for(int i=2; i*i<=n; i++)
    {
        if(tab[i-2]==false)
        {
            for(int j=i*2; j<=n; j+=i)
            {
                tab[j-2]=true; //zaczynamy od pierwszej z kolei szufladki a nie od trzeciej 
            }
        }
        else //wiem że to nie jest potrzebne ale dałem do eksperymentu :)
        {
            continue;
        }
    }

    for(int i=2; i<=n; i++)
    {
        if(tab[i-2]==false)
        {
            cout<<i<<"\t";
        }
    }

    delete [] tab;

    return 0;
}