O sicie Eratostenesa - najstarsze sito liczb pierwszych
Sito Eratostenesa znajduje wszystkie liczby pierwsze do zadanej granicy bez ani jednego dzielenia. Wystarczy liczyć: po 2 skreśl co drugą liczbę, po 3 co trzecią i tak dalej. To, co zostanie, to liczby pierwsze. Ponad dwa tysiące lat później to wciąż jeden z najszybszych sposobów, by je wypisać.
Eratostenes z Cyreny
Eratostenes żył mniej więcej od 276 do 194 p.n.e. i kierował wielką Biblioteką Aleksandryjską. Najbardziej znany jest z tego, że zmierzył wielkość Ziemi na podstawie długości cieni w dwóch miastach. Sito nosi jego imię, ponieważ Nikomach z Gerazy opisał je jako jego metodę we Wstępie do arytmetyki, napisanym około 100 roku n.e.
Jak działa sito
Zapisz liczby od 2 do N. Pierwsza liczba, 2, jest pierwsza: skreśl 4, 6, 8 i każdą inną wielokrotność 2. Następna liczba, która została, 3, jest pierwsza: skreśl 9, 12, 15 i tak dalej. Kontynuuj z 5, 7 i kolejnymi pozostałymi liczbami. Liczba, która nigdy nie zostanie skreślona, nie ma mniejszego dzielnika, więc jest pierwsza.
Zatrzymaj się na pierwiastku
Każda liczba złożona do N ma dzielnik pierwszy nie większy niż pierwiastek z N. Gdy więc p² przekroczy N, nie ma już czego skreślać. Do znalezienia liczb pierwszych do 100 wystarczą 2, 3, 5 i 7, a do 1000 liczby pierwsze do 31.
Jak szybkie jest sito?
Sito potrzebuje około N log log N kroków, a to rośnie tylko trochę szybciej niż samo N. Komputery wciąż go używają, często po kawałku jako sita segmentowego, aby wypisać liczby pierwsze aż do miliardów. Do sprawdzenia, czy jedna duża liczba jest pierwsza, szybsze są inne metody.
Często zadawane pytania
Kto wymyślił sito Eratostenesa?
Nosi imię Eratostenesa z Cyreny, greckiego uczonego z III wieku p.n.e. Najstarszy zachowany opis pochodzi od Nikomacha z Gerazy, około 100 roku n.e.
Dlaczego sito zaczyna skreślać od p²?
Każda mniejsza wielokrotność p ma mniejszy dzielnik pierwszy, więc mniejsza liczba pierwsza już ją skreśliła.
Ile jest liczb pierwszych poniżej 1000?
Poniżej 1000 jest 168 liczb pierwszych. Największa z nich to 997.
Powiązane narzędzia
Sito Eratostenesa
Zobacz, jak sito Eratostenesa znajduje liczby pierwsze do 100, 200, 500 lub 1000. Każda liczba pierwsza skreśla swoje wielokrotności własnym kolorem, krok po kroku.
Spirala Ulama
Narysuj spiralę Ulama w przeglądarce. Zaznacz liczby pierwsze, odczytaj wielomian kwadratowy każdej przekątnej i otwórz nieprzerwany ciąg 40 liczb pierwszych Eulera.
Spirala Ulama
Jak spirala Stanisława Ulama z 1963 roku układa liczby całkowite na kwadratowej siatce, dlaczego liczby pierwsze gromadzą się na kwadratowych przekątnych i gdzie leży czterdzieści liczb pierwszych Eulera, gdy spirala zaczyna się od 41.
Hipoteza Collatza
Poznaj problem Collatza 3n+1 w przeglądarce. Śledź ciągi gradowe, wyhoduj geometryczne drzewo Collatza i przybliżaj ciągły fraktal Collatza.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Wypróbuj sito Eratostenesa