Sito Eratostenesa — schemat blokowy
Odkrywaj liczby pierwsze, skreślając wielokrotności kolejnych liczb. Schemat pokazuje, którą instrukcję właśnie wykonujesz.
Schemat blokowy
Zielony blok — aktualny etap algorytmu. „Skreśl wielokrotności” jest pokazywane po jednej liczbie, dzięki czemu widać odsiewanie.
Odsiewanie liczb
🟩 Pierwsza ◉ Aktualna liczba pierwsza ■ Nowo skreślona ~~ Przekreślona
Historia działań
Wynik
Jeszcze nie wyznaczono.
Dlaczego to działa?
Każda liczba złożona ma dzielnik pierwszy nie większy od swojego pierwiastka kwadratowego. Dlatego wystarczy wybierać liczby p ≤ √N. Dla każdej nieskreślonej liczby p skreślamy jej wielokrotności, zaczynając od p² — mniejsze wielokrotności zostały już skreślone wcześniej.
Na przykład dla N = 30: najpierw skreślamy wielokrotności 2, później 3 i 5. Nieskreślone liczby to 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.