[C++] Sito Eratostenesa

[Luminofor]

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;
}

[MiW]

Używaj komentarzy, jeżeli chcesz, by ktoś ci pomógl.
1. i<n lub tablica [101]
2. j*k<n

[Luminofor]

Ok dzięki za rady, poprawny kod:

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?

[ Dodano: 2009-04-22, 21:29 ]
Wymodziłem kod do 10 milionów:

Kod: Zaznacz cały

#include <iostream>

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<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;
}

[aktus]

Jak chcesz przyśpieszyć wykonanie programu, to testuj tylko liczby nieparzyste. Wszystkie parzyste mają dodatkowy dzielnik 2, więc one już odpadają.

[olo16]

Taa... Tyle że 2 to też liczba pierwsza .

[aktus]

Widzisz problem mechanicznie dodać do tablicy liczbę 2?

[DarkJarek]

Jeżeli chcesz zaoszczędzić miejsca i czasu możesz zastosować taki myk: robisz sobie tablicę powiedzmy 100-elementową charów i każdy char to 8 liczb(bitów). Na początku inicjalizujesz całą tablicę wartością 0xAA co od razu załatwia wszystkie liczby parzyste. I jeszcze mała rada: jak jakaś liczba ma już ustawione 0 to nie warto sprawdzać jej wielokrotności bo one na pewno są już zerami.

[aktus]

No normalnie nie wiem o co ci kaman.

[Luminofor]

Pewnie o to, że AA w hexie to 01010101 w dwójkowym i to załatwia parzyste, nice idea