Sito Eratostenesa: schemat blokowy, algorytm i implementacja

Sito Eratostenesa jest algorytmem, którego autorem jest Eratostenes z Cyreny. Jest to postać znana z wyznaczenia obwodu Ziemi oraz oszacowania odległości Słońca i Księżyca względem naszej planety.

Sito Eratostenesa służy do wyznaczania liczb pierwszych z zadanego przedziału, od 2 do n. Dla przypomnienia: liczba pierwsza to taka, która ma dokładnie dwa różne dzielniki: 1 oraz samą siebie. Z tego powodu wartość 1 nie jest liczbą pierwszą, najmniejszą taką liczbą jest 2.

Co to jest Sito Eratostenesa?

Działanie algorytmu opiera się na zasadzie, która wynika bezpośrednio z definicji liczby pierwszej. W pierwszym kroku tworzymy tablicę, w której wszystkie wartości wynoszą “prawda”. Każda z nich będzie odpowiadała jednej liczbie z naszego przedziału. Wybieramy najmniejszą liczbę pierwszą z tego przedziału – jest nią 2. Następnie, dla wartości kolejno 4, 6, 8…, czyli wszystkich wielokrotności tej liczby większych od niej samej, komórki ustawiamy na fałsz. W następnym kroku należy wybrać kolejną liczbę z przedziału, dla której odpowiadająca komórka ma wartość prawda. Powtarzamy te kroki aż do momentu, w którym nie wykluczymy wielokrotności wszystkich liczb.

Sito eratostenesa gif
Sito Eratostenesa działa na zasadzie eliminacji wielokrotności liczb pierwszych. Zaczynając od liczby 2, oznaczanej jako pierwsza liczba pierwsza, algorytm eliminuje wszystkie jej wielokrotności. Następnie przechodzi do kolejnej nieoznaczonej liczby i powtarza proces.

Wartości, których komórki mają wartość prawda, to liczby pierwsze. Zauważmy, że górną granicą pętli, która przechodzi po liczbach, jakich wielokrotności sprawdzamy, jest pierwiastek z n. Pozwala to na znaczne przyspieszenie działania programu.

Przeanalizujmy działanie tego algorytmu dla n=16. Początkowo nasza tabela prezentuje się tak:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Dla wszystkich podanych tutaj wartości, zawartość tablicy jest równa prawda. Teraz zaznaczmy na czerwono wszystkie wielokrotności liczby 2 (większe od niej samej).

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Teraz powtórzmy ten proces dla liczby 3.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Kolejnym krokiem byłoby zaznaczenie wielokrotności liczby 5, jednak byłaby ona większa, niż pierwiastek z n. Oznacza to, że wykonywanie naszego algorytmu zakończyło się. Liczby niezamalowane na czerwono są liczbami pierwszymi. Wynik naszego algorytmu to zatem:

2, 3, 5, 7, 11, 13

Złożoność pamięciowa tego algorytmu to O(n), czyli liniowa – w przypadku dużych liczb może ona okazać się problemem. Złożoność obliczeniowa to  O(n log log n). Choć jest to bardzo nietypowa złożoność, oznacza to, że nasz algorytm jest relatywnie szybki.

Sito eratostenesa - Schemat Blokowy
Indeksacja tablic ma zakres od 1 do n. To przykład algorytmu “wyszukiwania wykluczającego” (ang. sieve), który polega na stopniowym wykluczaniu liczb niepożądanych, aby ostatecznie uzyskać wynik. Powyższy schemat wykreśla wielokrotności wszystkich liczb.

Pseudokod – Sito Eratostenesa:

Należy pamiętać, że indeksacja tablic wynosi od 1 do n.

Co ciekawe Sito Eratostenesa jest jednym z najstarszych i najbardziej skutecznych algorytmów do znajdowania liczb pierwszych. Został on opisany przez Eratostenesa w III wieku p.n.e. Algorytm ten był używany już przez starożytnych Greków do znajdowania liczb pierwszych.

ads banner

Sito Eratostenesa – Python:

Sito Eratostenesa – C++:

Sito Eratostenesa – Java:

Podsumowanie – Liczby pierwsze w zasięgu Twojej ręki

Sito Eratostenesa to stosunkowo prosty algorytm, który umożliwia wykluczenie określonych wielokrotności jako liczb złożonych (czyli niepierwszych). Okazuje się to niezwykle przydatne w teorii liczb, z której podstawami zapewne udało Ci się już zapoznać w ramach nauki szkolnej. Zapoznaj się z implementacją tego algorytmu w różnych językach (C++, Python i Java), a także postaraj się zmodyfikować jego działanie, co ułatwi Ci zrozumienie zasady działania.

Najczęściej zadawane pytania o Sito Eratostenesa

Czy algorytm sita Eratostenesa jest skuteczny dla dużych liczb?

Wydajność sita Eratostenesa może się pogorszyć wraz ze wzrostem rozmiaru zbioru liczb (pewną pomocą okazuje się optymalizacja). Dla bardzo dużych wartości może być bardziej efektywne zastosowanie innych algorytmów generujących liczby pierwsze.

Jakie są możliwe zastosowania algorytmu sita Eratostenesa?

Przede wszystkim ten algorytm okazuje się pomocny w przypadku teorii liczb, gdzie w wielu działaniach istnieje potrzeba wygenerowania liczb pierwszych. Podobnie jeśli chodzi o określenie czy konkretne wartości są pierwsze, można uznać sito Eratostenesa za przydatne.

Jakie są inne algorytmy podobne do sita Eratostenesa?

Liczby pierwsze okazują się niezwykle ważne w wielu przypadkach, dlatego powstały rozmaite rozwiązania, które mają na celu ich sprawdzanie lub generowanie liczb pierwszych. Wśród najpopularniejszych algorytmów można wymienić:

  • Test Millera-Rabina,
  • Sito Atkina,
  • Sito Sundarama.
Jakie są ograniczenia algorytmu sita Eratostenesa?

Głównym ograniczeniem jest zapotrzebowanie na dużą ilość pamięci, ze względu na tworzenie tablicy równej zakresowi zbioru liczb, który jest wykorzystywany.

ads banner

Wpisy, które mogą Cię zainteresować: