Sito Eratostenesa – schemat blokowy, algorytm i implementacja

Sito Eratostenesa jest jednym z najstarszych – zostało opisane w III w. p.n.e. i było używane już przez starożytnych Greków – oraz najskuteczniejszych algorytmów do znajdowania liczb pierwszych.

Co to jest Sito Eratostenesa?

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.

Sito Eratostenesa to algorytm, 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 od naszej planety.

Złożoność pamięciowa Sita Eratostenesa to O(n), czyli liniowa – co w przypadku dużych liczb może okazać się problemem, natomiast 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.

Kalkulator – Sito Eratostenesa

Jak działa Sito Eratostenesa?

Działanie algorytmu opiera się na zasadzie, która wynika bezpośrednio z definicji liczby pierwszej. Otóż w pierwszym kroku tworzymy tablicę, w której wszystkie wartości opisujemy jako „prawda” (każda z nich będzie odpowiadała jednej liczbie z naszego przedziału). W dalszej kolejności wybieramy najmniejszą liczbę pierwszą z tego przedziału – jest nią 2. Następnie, dla wartości kolejno 4, 6, 8… (czyli dla wszystkich wielokrotności tej liczby większych od niej samej) komórki ustawiamy na „fałsz”, po czym wybieramy 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.

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 oznaczamy jako „prawda”, to liczby pierwsze. Zauważmy, że górną granicą pętli, która przechodzi po liczbach, jakich wielokrotności sprawdzamy, jest n.

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

Dalej powtórzmy ten proces dla liczby 3 (wielokrotności zaznaczmy tym razem na fioletowo).

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

Następnie robimy tak samo z liczbą 5 (jej wielokrotności zaznaczając na niebiesko)…

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

…i liczbą 7 (zielony).

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

Kolejno powinniśmy zaznaczać liczby 11 i 13, jednak ich wielokrotności są większe od 16 (czyli zakresu sprawdzanych wartości), więc nie doprowadzi to do żadnych zmian.

Liczby, które pozostały zaznaczone na czarno, to liczby pierwsze. Ostateczny wynik wygląda zatem tak:

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

Z tego wynika, że liczby pierwsze znalezione w zakresie od 2 do 16 to:

2, 3, 5, 7, 11, 13

Sito Eratostenesa – Schemat blokowy i pseudokod

Poniżej znajdziesz Sito Eratostenesa w formie podstawowej, bez żadnych dodatkowych usprawnień. Okazuje się idealne, dla zrozumienia działania tego algorytmu.

Pseudokod – Sito Eratostenesa

Opis Sita Eratostenesa – Pseudokod

• 1 linia – Deklaracja funkcji sitoEratostenesa, przyjmującej argument n.
• 2 linia – Tworzenie tablicy liczbyPierwsze o rozmiarze od 1 do n. Tablica ta będzie przechowywać informacje o liczbach pierwszych od 1 do liczby n.
• 3 linia – Pętla od 1 do n.
• 4 linia – Zmiana wszystkich elementów tablicy liczbyPierwsze jako prawda (true).
• 5 linia – Ustawienie wartości dla pierwszego elementu tablicy liczbyPierwsze jako fałsz (false), ponieważ 1 nie jest liczbą pierwszą.
• 6 linia – Druga pętla, iteracja od 2 do n.
• 7 linia – Sprawdzenie czy element tablicy o indeksie i jest oznaczony jako liczba pierwsza.
• 8 linia – Zmienna j równa się i + i, czyli pierwsza wielokrotność danej liczby. Pętla iteruje od i + i do n z krokiem i, oznaczając wszystkie wielokrotności i jako niebędące liczbami pierwszymi, ustawiając odpowiednie wartości w tablicy liczbyPierwsze na fałsz (false).
• 9 linia – Pętla z warunkiem sprawdzającym, czy zmienna j jest mniejsza lub równa n. Pozwala to sprawdzać wielokrotności, które nie przekraczają n (zakresu przeszukiwanych wartości)
• 10 linia – Przypisanie fałsz (false), do elementu tablicy odpowiadającemu wielokrotności liczby i.
• 11 linia – Dodanie do zmiennej j wartości i. Pozwala to zająć się kolejną wielokrotnością liczby.
• 12 linia – Zwrócenie tablicy liczbyPierwsze, która zawiera informacje o liczbach pierwszych od 1 do liczby n.

Sito Eratostenesa – Python, C++ i Java

Sito Eratostenesa zoptymalizowane – Schemat blokowy i pseudokod

W następującym pseudokodzie oraz schemacie blokowym, możesz znaleźć optymalizacje, dzięki którym Sito Eratostenesa zaczyna działać wydajniej. Ich wytłumaczenie znajdziesz w opisie pseudokodu.

Pseudokod – Zoptymalizowane Sito Eratostenesa

Opis zoptymalizowanego Sita Eratostenesa – Pseudokod

• 6 linia – Iteracja do pierwiastka kwadratowego z n: Zamiast iterować od 2 do n (jak w wersji podstawowej), gdzie n jest górnym zakresem, iterujemy tylko do pierwiastka kwadratowego z n, czyli i * i ≤ n (bo i ≤ pierwiastek(n) podniesiony do kwadratu, to: i * i ≤ n). Wynika to z faktu, że jeśli n nie jest liczbą pierwszą, to musi mieć przynajmniej jeden dzielnik mniejszy lub równy jego pierwiastkowi kwadratowemu. Dlatego nie ma potrzeby sprawdzania wielokrotności liczb większych niż pierwiastek kwadratowy z n.
  Ograniczamy więc ilość iteracji, przykładowo gdy n = 16, jeśli sprawdza się wielokrotności liczb do n, to rozpoczyna się też sprawdzanie wielokrotności liczby 11, której wielokrotność jest przecież większa od n, więc pętla się rozpoczyna i natychmiast zakańcza. Takie działanie jest niepotrzebne, czemu potrafi zapobiec ta optymalizacja.
• 8 – 10 linia – Początek od i * i: Wewnętrzna pętla iteruje od i * i zamiast od 2 * i. Dzieje się tak dlatego, że wszystkie mniejsze wielokrotności liczby i już zostały oznaczone jako niebędące liczbami pierwszymi przez poprzednie iteracje. Rozpoczynając od i * i pomijamy już zaznaczone wielokrotności, co znacznie redukuje liczbę operacji. Czyli przykładowo, gdy i = 3, zamiast stosować: 3 + 3 = 6, a następnie 3 + 3 + 3= 9, używa się od razu 3 * 3 = 9, co pozwala zmniejszyć liczbę operacji.

Sito Eratostenesa zoptymalizowane – Python, C++ i 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ę on niezwykle przydatny w teorii liczb, której podstawy poznałeś w szkole. Zapoznaj się z implementacją tego algorytmu w różnych językach (C++, Python i Java), a także postaraj się zmodyfikować jego działanie, dzięki czemu łatwiej ci będzie zrozumieć zasady postępowania przy korzystaniu z niego.

Najczęściej zadawane pytania o Sito Eratostenesa

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