[C++] Sito Eratostenesa

Forum dotyczące ogólnie pojętego programowania - algorytmów, struktur danych, narzędzi programistycznych, itp - głównie w kontekście komputerów PC.
ODPOWIEDZ
Awatar użytkownika
Luminofor
Użytkownik
Posty: 1375
Rejestracja: 27 lis 2007, 17:17
Lokalizacja: Polska

[C++] Sito Eratostenesa

Post autor: Luminofor » 22 kwie 2009, 18:13

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żytkownik
Posty: 226
Rejestracja: 28 sty 2007, 11:32
Lokalizacja: Kraków
Kontakt:

Post autor: MiW » 22 kwie 2009, 18:31

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

Awatar użytkownika
Luminofor
Użytkownik
Posty: 1375
Rejestracja: 27 lis 2007, 17:17
Lokalizacja: Polska

Post autor: Luminofor » 22 kwie 2009, 19:18

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;
}
Ostatnio zmieniony 23 kwie 2009, 17:01 przez Luminofor, łącznie zmieniany 2 razy.

aktus
Użytkownik
Posty: 379
Rejestracja: 06 sie 2007, 20:44
Lokalizacja: Tychy

Post autor: aktus » 23 kwie 2009, 11:55

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

Awatar użytkownika
olo16
Użytkownik
Posty: 396
Rejestracja: 12 paź 2007, 16:37
Lokalizacja: w-wa

Post autor: olo16 » 24 kwie 2009, 12:54

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

aktus
Użytkownik
Posty: 379
Rejestracja: 06 sie 2007, 20:44
Lokalizacja: Tychy

Post autor: aktus » 24 kwie 2009, 14:49

Widzisz problem mechanicznie dodać do tablicy liczbę 2?

Awatar użytkownika
DarkJarek
-
Posty: 44
Rejestracja: 21 mar 2006, 15:48
Lokalizacja: ...
Kontakt:

Post autor: DarkJarek » 24 kwie 2009, 20:05

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
Użytkownik
Posty: 379
Rejestracja: 06 sie 2007, 20:44
Lokalizacja: Tychy

Post autor: aktus » 25 kwie 2009, 0:46

No normalnie nie wiem o co ci kaman.

Awatar użytkownika
Luminofor
Użytkownik
Posty: 1375
Rejestracja: 27 lis 2007, 17:17
Lokalizacja: Polska

Post autor: Luminofor » 25 kwie 2009, 0:48

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

ODPOWIEDZ