Problem z zakresem wartości

Question

Cześć, zajmuję się aktualnie problemem wypisywania liczb pierwszych z zakresu <1;n> i napisałem program (sito Eratostenesa) który ogólnie działa ale są dwie rzeczy których nie rozumiem. Kod:

#include <iostream>

using namespace std;

int main()
{
    int n;

    cin>>n;

    n += 1;
    int t[n];
    t[0] = 0;
    t[1] = 0;

    for(int j = 2; j <= n; j++)
    {
        t[j] = 1;
    }

    for(int i = 2; i <= n; i++)
    {
        if(t[i] == 1 && i*i <= n)
        {
            for(int x = i*i; x <=n; x+=i)
                t[x] = 0;
        }
    }

    for(int k = 1; k <= n; k++)
    {
        if(t[k] == 1)
            cout<<k<<"  ";
    }


    return 0;
}

1. Zakres wartości - tutaj wszędzie użyłem int, próbowałem z long long ale problem polega na tym, że program przestaje działać dla n dużo mniejszego od maksymalnej wartości danego typu danych, Przykładowo dla int program nie działa dla n = 100 000 a maksymalną wartością dla int jest chyba ponad 2 000 000 000 więc dużo więcej i tutaj pojawia się moje pytanie - dlaczego program nie działa dla wartości większych? Dodam że jak użyłem long long to granica się podniosła, ale dla 260 000 nie działał a zakres jest dużo większy

2. Druga sprawa to tablice - jak deklaruję tablicę int t[5] to zawiera ona elementy t[0] t[1] t[2] t[3] t[4]. Ja w programie wpisuję n i dalej dodaję 1 do tego n (n += 1) tak żeby tablica t[n] zawierała elementy od t[0] do t[n]. Jak to zatem możliwe że po uruchomieniu programu i wpisaniu 100 ostatnią wypisaną przez program liczbą jest 101?

Comments

Ten kod:

cin>>n;
...
int t[n];

Jest niezgodny ze standardem języka C++. VLA jest poprawne np. w C, choć z tego co wiem to nie jest zalecane.

Answer 1

Masz tam mnożenie i * i dla wartości i od 0 do <= n więc gdy n = 100 000 to i * i = 10 000 000 000 a zakres int-a to od -2 147 483 648 do 2 147 483 647

Poza tym działasz na liczbach naturalnych więc lepiej używać unsigned int

Comments

Ok, tylko mam pytanie bo jest tam to i*i i to działanie nie jest przypisane do żadnej zmiennej, jest za to porównywane z int, więc jak to dokładnie działa - jak mamy porównanie int i działania to to działanie komputer bierze za inta? Albo ogólnie mamy porównanie zmiennej i działania to to działanie jest widziane jako zmienna takiego typu jak ta z którą porównujemy?

---

C++ traktuje wszystkie stałe całkowite jako wartość typu int, o ile nie występują wyjątki.

Pierwszym wyjątkiem jest dodanie do stałej przyrostka określającego typ, drugim wartość zbyt duża dla int.

---

Tak to jest porównanie int-a z int-em bo operator mnożenia dla tych dwóch wartości zwraca wartość typu int. Operatory to są też funkcje, które realizują zazwyczaj pewne podstawowe matematyczne działania.

---

Pierwszym wyjątkiem jest dodanie do stałej przyrostka określającego typ, drugim wartość zbyt duża dla int.

Skoro tak to czy w tym przypadku nie powinien to być wyjątek (zbyt duża dla int)?

 

---

Tak to jest wyjątek. Kiedy wartość stałej całkowitej przekracza zakres int, zostaje zmieniona na taką, która może ją pomieścić.

Answer 2

1. Możliwe, że brakuje Ci pamięci ram. Rezerwowanie  260000 zmiennych to duży ubytek pamięci.

Maksymalną wartość zmiennej możesz sprawdzić stosując bibliotekę <climits>.

Przykładowo:

#include <iostream>
#include <climits>

int main ()
{
          std::cout<<INT_MAX; // pokaz maksymalna wartosc int
          std::cout<<std::endl<<INT_MIN;  // pokaz minimalna wartosc int        
          return 0;
}

2.

Linijka n += 1; zwiększa n o 1. Więc po wpisaniu 100 twój program dodaje jedynkę i rezerwuje t[n] czyli t[101].

Comments

1.Myślę że nie bo raz że mam 8GB i tylko ten program działał a dwa że dla int granicą była dużo niżej niż long long więc to zależy od typu

2.jak deklaruje aż tablice int t[5] to nie możesz potem w programie napisać t[5] = 8; bo taki element nie istnieje (istnieją od 0 do 4 i w sumie jest ich 5)