Co odsiewa sito Eratostenesa?

Czytając matematyczną literaturę, czasami można się natknąć na różne ciekawe obiekty, np. dywan (Sierpińskiego), wstęga (Mobiusa), butelka (Kleina), pierścień (Gaussa) czy łańcuch (Markowa). Dziś na warsztat weźmiemy sito, a konkretnie sito Eratostenesa.

Wszelkiego rodzaju sita i sitka charakteryzują się tym, że oddzielają od siebie pewne obiekty, mają otwory, które przepuszczają mniejsze cząsteczki, a zatrzymują większe.

Sito Eratostenesa odsiewa liczby złożone, a zostawia liczby pierwsze. Nazwa pochodzi od Eratostenesa z Cyreny, który żył na przełomie III i II wieku p.n.e.

Sito Eratostenesa to algorytm znajdowania liczb pierwszych mniejszych od danej liczby.

Przypomnę, jeśli nie pamiętasz, że liczby pierwsze to takie, które są podzielne tylko przez siebie i przez 1, wiec są one pod tym względem specjalne (oto kilka pierwszych liczb pierwszych: 2, 3, 5, 7, 11, ...).

Dla przykładu, jak szybko znaleźć liczby pierwsze mniejsze od 100? Przy małych liczbach jeszcze jest łatwo sprawdzić, przez co się dzielą, ale jak na przykład dowiedzieć się, czy taka liczba 97 jest pierwsza?

Oczywiście można szukać wszystkich dzielników pojedynczo dla każdej liczby, ale po co, skoro można to szybko zrobić hurtowo.

Algorytm wygląda następująco:

- Wypisuję liczby od 1 do 100

- Skreślam jedynkę (przypomnę, że nie jest ani pierwsza ani złożona)

- Wybieram najmniejszą nieskreśloną liczbę i wykreślam wszystkie jej wielokrotności większe od niej

- Powtarzam powyższy krok aż najmniejsza liczba przekroczy pierwiastek ze 100

- Nieskreślone liczby to liczby pierwsze

Powyżej został podany przepis, zastosujmy go teraz w praktyce:

- wypisuję liczby od 1 do 100

- wykreślam jedynkę

- najmniejsza nieskreślona jest dwójka, wykreślam jej wielokrotności, skacząc co 2, czyli: 4, 6, 8 10, ..., 98, 100

- najmniejszą nieskreśloną jest trójka, więc wykreślam jej wielokrotności: 6, 9, 12, ... , 96, 99

- czwórka już jest skreślona, idę dalej

- kolejna jest piątka, więc wykreślam: 10, 15, 20, ..., 95, 100

- szóstka już jest skreślona, idę dalej

- kolejna jest siódemka, więc wykreślam: 14, 21, ... 91, 98

- ósemka, dziewiątka i dziesiątka są już skreślone, idę dalej

- kolejna jest 11, jest większa niż 10 (pierwiastek ze 100), więc kończę procedurę

- niewykreślone są: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 - są to liczby pierwsze

Źródło grafiki: Wikipedia

Wyjaśnienia dla dociekliwych:

- skreślamy wielokrotności danej liczby k, bo mamy pewność, że nie są one pierwsze, gdyż są podzielne przez tę liczbę k

- pomijamy liczby już wykreślone, bo skoro są wykreślone, to dzielą się przez jakąś liczbę k, więc na pewno wszystkie jej wielokrotności też już zostały wykreślone przy okazji k (np. dla szóstki, już przy krokach dla 2 oraz dla 3 wykreśliliśmy wszystkie wielokrotności 6, czyli 12, 18, ..., 96)

- kończymy algorytm na pierwiastku ze 100, bo jeśli jakaś liczba byłaby podzielna przez liczbę większą od 10, to też musiałaby mieć dzielnik mniejszy niż 10, więc już jest skreślona (gdyby tak nie było, to oba dzielniki, które po wymnożeniu dają tę liczbę, byłyby większe od 10, więc ta liczba musiałaby być większa niż 100, a nas interesują liczby od 1 do 100), np. nie muszę wykreślać wielokrotności 11, bo wszystkie liczby 22, 33, 44, ..., 99 już zostały skreślone przy okazji 2, 3, 4, ..., 9 odpowiednio, a liczba 11*10=110 już jest poza naszym zakresem

Ciekawostka dla osób uczących się programować: algorytm oparty na sicie Eratostenesa pojawia się jako jeden z przykładów zastosowania pętli.

____________

Jeśli chcesz poćwiczyć działanie sita Eratostenesa, sprawdź, ile jest liczb pierwszych między 1 a 200. Odpowiedź podam w komentarzu.

# Odpowiedź: 46