Sito Eratostenesa - jak znaleźć liczby pierwsze? Poradnik

Sito Eratostenesa to prosty, a jednocześnie bardzo elegancki sposób na wyłuskanie liczb pierwszych z całego przedziału. W tym artykule pokazuję, na czym polega ta metoda, jak przeprowadzić ją ręcznie, gdzie najłatwiej o błąd i kiedy lepiej sięgnąć po inne podejście. To temat przydatny zarówno na matematyce, jak i przy pierwszych krokach w informatyce, bo uczy myślenia krok po kroku zamiast zgadywania wyniku.

Czym jest sito Eratostenesa i po co się je poznaje

Jeśli mam wskazać jedną rzecz, którą ten algorytm robi wyjątkowo dobrze, to jest nią porządkowanie chaosu. Zamiast sprawdzać każdą liczbę osobno i pytać, czy ma dzielnik, budujesz listę od 2 do n, a potem usuwasz wszystko, co na pewno nie jest pierwsze. Ja traktuję to jako świetny przykład algorytmu, który pokazuje sens pracy na zbiorze, a nie na pojedynczym elemencie.

Najważniejsza idea jest prosta: nie szukasz liczb pierwszych przez zgadywanie, tylko przez eliminację wielokrotności liczb, które już rozpoznano jako pierwsze. W praktyce oznacza to, że 1 od razu wypada z gry, 2 zostaje pierwszą liczbą pierwszą, a potem kolejne kroki robią resztę pracy. Nazwa nawiązuje do Eratostenesa z Cyreny, ale sama metoda jest tak użyteczna, że nadal świetnie nadaje się do nauki logiki algorytmicznej.

To właśnie dlatego algorytm pojawia się nie tylko w matematyce, lecz także w informatyce. Uczy rozumienia wielokrotności, działania na tablicach i pracy według reguły, która daje przewidywalny wynik. A skoro wiemy już, po co go poznaje się na lekcjach, przejdźmy do samego mechanizmu.

Jak działa algorytm krok po kroku

W wersji szkolnej najlepiej wyobrazić sobie długi ciąg liczb zapisanych na kartce albo w tabeli. Potem po prostu skreślasz kolejne wielokrotności. Jeśli pokazuję ten temat uczniom, zwykle zaczynam od małego zakresu, bo wtedy reguła staje się widoczna niemal od razu.

1. Zapisz wszystkie liczby od 2 do n.
2. Zostaw 2, a skreśl jej większe wielokrotności: 4, 6, 8, 10 i tak dalej.
3. Przejdź do następnej nieskreślonej liczby, czyli 3, i skreśl jej wielokrotności: 6, 9, 12, 15, 18.
4. Kontynuuj dla kolejnych nieskreślonych liczb: 5, 7, 11...
5. Zakończ, gdy dojdziesz do liczby nie większej niż pierwiastek z n.
6. Wszystkie liczby, które pozostały nieskreślone, są liczbami pierwszymi.

Dlaczego wystarczy dojść do pierwiastka

To moment, który często sprawia uczniom trudność, więc tłumaczę go bardzo dosłownie. Jeśli liczba złożona ma dwa czynniki większe od pierwiastka z n, to ich iloczyn byłby już większy niż n. A skoro szukasz tylko w zakresie do n, nie musisz sprawdzać dalej. Dzięki temu algorytm nie wykonuje zbędnej pracy.

W praktyce oznacza to też ważną oszczędność: nie skreślasz wszystkiego do końca w sposób chaotyczny, tylko zatrzymujesz się w odpowiednim miejscu. Żeby zobaczyć, jak to wygląda na konkretnych liczbach, przejdźmy teraz do małego przykładu.

Przykład dla liczb od 2 do 30

Najlepiej widać działanie sita, gdy zakres jest mały. Wtedy nie trzeba ufać pamięci, tylko można śledzić każdy ruch. Ja zwykle wybieram liczby do 30, bo to dobry kompromis między prostotą a czytelnością.

Wynik jest krótki i bardzo czytelny: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Właśnie dlatego ta metoda tak dobrze sprawdza się na początku nauki. Nie trzeba nic udowadniać „na wiarę”, bo każde skreślenie ma konkretne uzasadnienie. Teraz porównajmy to z prostszym, ale mniej eleganckim sposobem sprawdzania liczb pierwszych.

Kiedy to sito wygrywa z prostym sprawdzaniem dzielników

To ważne rozróżnienie, bo wiele osób myli te dwa podejścia. Jeśli chcesz sprawdzić jedną liczbę, zwykłe dzielenie przez kolejne potencjalne dzielniki do pierwiastka z liczby bywa wystarczające i często prostsze. Jeśli jednak potrzebujesz całej listy liczb pierwszych do n, sito ma wyraźną przewagę.

W praktyce decyduje skala problemu. Przy małym zadaniu szkolnym oba sposoby mogą być akceptowalne, ale przy większym zakresie sito staje się bardziej naturalne. Gdy pamięć zaczyna mieć znaczenie, wchodzi już kolejny poziom zaawansowania, czyli wersje odcinkowe albo inne odmiany sit, ale na start nie ma sensu ich mieszać z podstawową metodą. Zanim jednak uznasz temat za zamknięty, warto zobaczyć, gdzie najczęściej pojawiają się potknięcia.

Najczęstsze błędy przy nauce i rozwiązywaniu zadań

Ten algorytm wygląda prosto, ale właśnie przez to uczniowie łatwo wpadają w kilka powtarzalnych pułapek. Ja najczęściej widzę nie błąd w samym pomyśle, tylko w drobnym pominięciu kroku albo w złym uporządkowaniu działań. To da się szybko naprawić, jeśli wiesz, na co zwracać uwagę.

• Zaczynanie od 1 - 1 nie jest liczbą pierwszą, więc w ogóle nie powinno znaleźć się w wyniku.
• Skreślanie samych liczb pierwszych - skreślasz wielokrotności, a nie bazową liczbę pierwszą.
• Skreślanie od zbyt małej liczby - przy liczbie 5 nie zaczynasz od 10, 15, 20 bez sensu, jeśli wcześniej te wartości zostały już usunięte.
• Powtarzanie pracy - jeśli dana liczba została już skreślona, nie oznacza to błędu; to po prostu normalny efekt uboczny pracy sita.
• Mylenie zakresu działania z testem pojedynczej liczby - sito służy do całej listy, nie do jednego „czy jest pierwsza?”
• Brak kontroli do pierwiastka - bez tego łatwo albo skończyć za wcześnie, albo wykonywać zbędne kroki.

Przeczytaj również: Ile cyfr ma numer legitymacji szkolnej? Poznaj standardy

Co naprawdę oznacza skreślanie od p²

To mały detal, ale bardzo ważny. Gdy dochodzisz do kolejnej liczby pierwszej p, sensownie jest zaczynać od p², a nie od 2p. Dlaczego? Bo wszystkie mniejsze wielokrotności tej liczby zostały już wcześniej wyłapane przez mniejsze liczby pierwsze. Taki skrót nie zmienia wyniku, ale oszczędza pracę i porządkuje tok rozumowania.

Jeśli ten moment jest jasny, cała metoda robi się znacznie bardziej logiczna. I właśnie dlatego warto od razu zobaczyć, gdzie to podejście naprawdę się przydaje, zamiast traktować je wyłącznie jako szkolną ciekawostkę.

Gdzie ten algorytm naprawdę się przydaje

W matematyce sito jest świetnym narzędziem do ćwiczenia pojęć związanych z dzielnikami, wielokrotnościami i liczbami pierwszymi. W informatyce ma jeszcze jedną zaletę: pokazuje, że dobrze zorganizowana tablica i prosty schemat potrafią dać bardzo mocny wynik. Ja lubię takie przykłady, bo uczą szacunku do prostych, ale dobrze zaprojektowanych rozwiązań.

• Na lekcji matematyki - pomaga szybko pokazać, czym są liczby pierwsze i dlaczego 1 do nich nie należy.
• Przy powtórce przed sprawdzianem - pozwala przećwiczyć wielokrotności bez zgadywania.
• W pierwszych zadaniach z programowania - uczy pracy na tablicy boolowskiej, pętli i warunku stopu.
• W zadaniach konkursowych - sprawdza się, gdy trzeba szybko przygotować listę liczb pierwszych do pewnej granicy.
• Jako wstęp do bardziej zaawansowanych metod - dobrze buduje intuicję przed wersjami odcinkowymi i szybszymi odmianami sit.

Nie wszystko jednak da się załatwić tą samą metodą. Gdy zakres staje się bardzo duży, a pamięć jest ograniczona, trzeba już myśleć o wariantach bardziej oszczędnych. Na poziomie szkolnym i początkującym klasyczna wersja nadal pozostaje najlepszym punktem wyjścia. Zostaje jeszcze ostatnia rzecz: co warto zapamiętać, żeby temat nie rozmył się po jednym przeczytaniu.

Co warto zapamiętać, gdy wraca temat liczb pierwszych

Najkrótszy sens całego algorytmu można zamknąć w jednym zdaniu: zamiast sprawdzać wszystko osobno, eliminujesz to, co na pewno nie jest pierwsze. To właśnie ta zmiana myślenia robi największą różnicę. Nie chodzi o zapamiętanie gotowej procedury, ale o zrozumienie porządku, który za nią stoi.

• Zakres zaczyna się od 2, bo 1 nie jest pierwsza.
• Skreślasz wielokrotności, a nie same liczby pierwsze.
• Przechodzisz tylko przez nieskreślone liczby.
• Zatrzymujesz się przy pierwiastku z górnej granicy zakresu.
• Przy kolejnych liczbach pierwszych zaczynasz od ich kwadratu.

Jeśli chcesz utrwalić temat, narysuj najpierw zakres do 30, potem do 50 albo 100. Na tak małej skali od razu widać, że sito nie jest sztuczką, tylko bardzo uporządkowaną metodą pracy z wielokrotnościami. I właśnie dlatego wraca tak często w nauce matematyki i informatyki.