Chciałem napisać program na sito Eratostenesa, kompiluje się bez błędu ale przy uruchomieniu i podaniu n wywala błąd, że niby stos koło zmiennej tablica jest niszczony. Gdzie jest błąd?
#include
using namespace std;
int main()
{
int tablica[100],n;
cout << "Podaj n: ";
cin >> n;
for(int i=0; i<=n; i++)
{
tablica[i]=1;
}
for(int j=2; j
{
if(tablica[j]==1)
{
for(int k=2; k
tablica[j*k]=0;
}
}
for(int l=2; l
{
if (tablica[l]==1)
cout << l << endl;
}
return 0;
}
Ze względu na tę linijkę możliwe wartości n są mocno ograniczone - do 9, dla 10 maksimum j i k to 10, a wtedy odwoływałoby się już do nieistniejącego elementu tablicy o indeksie 100. Założę się, że nie o to Ci chodziło… przemyśl ten algorytm
#include
using namespace std;
int main()
{
int tablica[200000],n,licznik=0;
cout << "Podaj n: ";
cin >> n;
for(int i=0; i<=n; i++)
{
tablica[i]=1; // wstepne przygotowanie tablicy
}
for(int j=2; j
{
int k=j;
while(k
{
k=k+j; // wielokrotnosc danej liczby
tablica[k]=0; // wyzerowanie wielokrotnosci
}
}
for(int m=2; m
{
if (tablica[m]==1) // sprawdzamy, czy m-ty wyraz tablicy jest liczba pierwsza
{
cout << m << endl; // jezeli tak, to wypisujemy
licznik++; // ile liczb pierwszych?
}
}
cout << endl << "W zakresie od 0 do " << n << " znajduje sie " << licznik << " liczb pierwszych wypisanych powyzej." << endl;
return 0;
}
Znajduje liczby pierwsze do 100 tysięcy i je zlicza.
Tym samym sposobem? Potrzebujesz więcej czasu i pamięci. Tak więc
Przyśpieszyć algorytm
Zoptymalizować użycie pamięci. Na razie aby przechować informację czy liczba jest liczbą pierwszą czy nie, zużywasz sizeof(int) bajtów. Lepiej gdyby była to tablica bool - wtedy większa zmieści się w pamięci. A jeszcze lepiej kiedy na jedną liczbę przypadać będzie 1 bit - więc robisz operacje na bitach. Operacje na bitach pozwalają Ci przy okazji zrealizować punkt 1
#include
using namespace std;
bool tablica[20000000];
int main()
{
int n,licznik=0;
cout << "Podaj n: ";
cin >> n;
for(int i=0; i<=n; i++)
{
tablica[i]=1; // wstepne przygotowanie tablicy
}
for(int j=2; j
{
int k=j;
while(k
{
k=k+j; // wielokrotnosc danej liczby
tablica[k]=0; // wyzerowanie wielokrotnosci
}
}
for(int m=2; m
{
if (tablica[m]==1) // sprawdzamy, czy m-ty wuraz tablicy jest liczba pierwsza
{
cout << m << endl; // jezeli tak, to wypisujemy
licznik++; // ile liczb pierwszych?
}
}
cout << endl << "W zakresie od 0 do " << n << " znajduje sie " << licznik << " liczb pierwszych wypisanych powyzej." << endl;
return 0;
}
