Wolna encyklopedia

Sito Eratostenesa to algorytm kolejnego wybierania liczb pierwszych z ciągu liczb naturalnych.

Ze zbioru liczb naturalnych większych od jedności, tj. {2, 3, 4, ...}, wybieramy najmniejszą, czyli 2, i wykreślamy wszystkie jej wielokrotności większe od niej samej, to jest 4, 6, 8, ...

  2 3 -4- 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 -44- 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60


Z pozostałych liczb wybieramy najmniejszą niewykreśloną liczbę (3) i usuwamy wszystkie jej wielokrotności większe od niej samej: 6, 9, 12, ..., przy czym nie przejmujemy się tym, że niektóre liczby (na przykład 6 czy 12) będą skreślane więcej niż raz.

  2 3 -4- 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 -44- 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60


Według tej samej procedury postępujemy dla liczby 5.

  2 3 -4- 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 -44- 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60


Następnie dla 7, 11, 13; aż do sprawdzenia wszystkich niewykreślonych wcześniej liczb.

  2 3 -4- 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 -44- 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60


Dla danej liczby n wszystkie niewykreślone liczby mniejsze od n są liczbami pierwszymi.

  2 3 -4- 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 -44- 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60

Zapis algorytmu

Zapis algorytmu w języku C++

#include <iostream>
using namespace std;

const int n = 100;

bool numbersTable[n + 1]; // tablica o indeksach od 0 do 100 | wszystkie false (czyli: 0);

int main()
{
	for (int i = 2; i <= n; i++ ) // przeszukuj liczby od 2 do n, 0 i 1 nie są liczbami pierwszymi
	{
		if (numbersTable[i] == true) // jeżeli dana liczb jest już wykreślona
			continue; // to przejdź do kolejnej
		for (int j = 2 * i ; j <= n; j += i) // przejdź od liczby 2 * i do n przesuwając się o i
			numbersTable[j] = true; // i każdą z nich usuwaj ze zbioru
	}
	
	for (int i = 2; i <= n; i++) // przejdź liczby od 2 do n
		if (numbersTable[i] == false) // jeśli liczba nie została usunięta ze zbioru
			cout << i << " | "; // to ją wypisz
	return 0;
}

Zobacz też

Linki zewnętrzne

Źródło: „haslo,Sito_Eratostenesa”