[C++] Sito Eratostenesa

Darlington · Postautor: **Darlington** » 22 kwie 2009, o 18:14

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?

Kod: Zaznacz cały

#include <iostream>

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<n; j++)
	{
		if(tablica[j]==1)
		{
			for(int k=2; k<n; k++)
			tablica[j*k]=0;
		}
	}
	for(int l=2; l<n; l++)
	{
		if (tablica[l]==1)
		cout << l << endl;
	}
	return 0;
}

Darlington · Postautor: **Darlington** » 22 kwie 2009, o 19:22

JUż mam:

Kod: Zaznacz cały

#include <iostream>

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<n; j++)
	{
		int k=j;
		while(k<n)
		{
			k=k+j;						 // wielokrotnosc danej liczby
			tablica[k]=0;			    	// wyzerowanie wielokrotnosci
		}
	}

	for(int m=2; m<n; 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.

Jak znaleźć więcej liczb pierwszych?

pajaczek · Postautor: **pajaczek** » 22 kwie 2009, o 19:23

Jakie podałeś n?? (w tym pierwszym przykładzie, gdzie "niszczyłeś stos").

Darlington · Postautor: **Darlington** » 22 kwie 2009, o 19:28

100 000, można dojechać do 126 tysięcy, sprawdziłem (tablica 262 000 - elementowa), niewiele powyżej tej wartości program się kompiluje, ale podczas uruchomienia się wysypuje - chyba to max rozmiar tablicy...

EDIT: to pisałem z myślą o drugim, poprawnym kodzie .
W pierwszym kodzie dla n>10 się program wysypywał.

pajaczek · Postautor: **pajaczek** » 22 kwie 2009, o 19:45

W pierwszym kodzie dla n>10 się program wysypywał.

I bardzo dobrze twierdził.

Stos, bo tablica jest zmienną lokalną, a więc tworzoną na stosie.
Powyżej 10, bo co to ma być:

tablica[j*k]=0;

Ps. problem powinien być już przy n=10, nie n>10.

Darlington · Postautor: **Darlington** » 22 kwie 2009, o 19:49

Dobra wiem, jak tym algorytmem wyznaczyć wszystkie liczby pierwsze od 0 do powiedzmy miliona? Tablica wielowymiarowa? Wiele tablic?

[C++] Sito Eratostenesa

Kto jest online