[C++] Sito Eratostenesa


(Kanaliaon) #1

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;

}

(Sawyer47) #2

tablica[j*k]=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


(Kanaliaon) #3

Ok dzięki za rady, poprawny kod:

#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. :slight_smile:

Jak znaleźć więcej liczb pierwszych?


(Sawyer47) #4

Tym samym sposobem? Potrzebujesz więcej czasu i pamięci. Tak więc

1) Przyśpieszyć algorytm

2) 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


(pebal) #5

Optymalizować.

#include 

#include 


using namespace std;


int main()

{

  int n;


  cout << "Podaj n: ";

  cin >> n;	


  vector tablica(n + 1, true);


  for(int j = 2; j <= (int)sqrt((double)n); ++j)

  {

    if (tablica[j])

    {

      int k = j * 2;

      while(k <= n)

      {

        tablica[k] = false;

        k += j;

      }

    }

  }


  int licznik = 1;

  for(int m = 3; m <= n; m += 2)

  {

    if (tablica[m])

    {

      //cout << m << endl;

      licznik++;

    }

  }


  cout << endl << "W zakresie od 0 do " << n << " znajduje sie " << licznik << " liczb pierwszych wypisanych powyzej." << endl;

  return 0;

}

(Kanaliaon) #6

Ulepszony kod:

Przetestowałem do 10 milionów :slight_smile:

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

}

(pebal) #7

Wykonujesz wiele nadmiarowych operacji i alokujesz dwukrotnie więcej pamięci, niż potrzeba.

Skorzystaj z wektora binarnego (std::vector), gdyż alokuje ośmiokrotnie mniej pamięci, od tablicy bool[...].


(Jp17) #8

WItam wszystkich... Mam wielka prosbe... ma Ktos moze napisany program sito eratostenesa napisane w C???

prosze o pomoc

pozdrawiam