PL 
EnglishDomyślny
Українська🔢 Sito Eratostenesa — animowane wyszukiwanie liczb pierwszych
Obserwuj działanie sita Eratostenesa w czasie rzeczywistym. Skreślaj wielokrotności kolejnych liczb pierwszych i odkryj wszystkie liczby pierwsze do 10000. Zobacz odstępy między nimi, funkcję π(x) i twierdzenie o liczbach pierwszych.
O sicie Eratostenesa
Ta symulacja bezpośrednio implementuje klasyczne sito Eratostenesa (ok. 240 r. p.n.e.): zaczynając od tablicy logicznej, w której wszystkie wartości od 2 do N są ustawione na „prawda”, algorytm wielokrotnie znajduje kolejny nieoznaczony indeks p i — dopiero gdy p² ≤ N — oznacza jako złożone wszystkie wielokrotności p począwszy od p², pomijając te już wcześniej wyeliminowane. Wszystko, co pozostaje nieoznaczone po zakończeniu sita, jest liczbą pierwszą. Każdy krok animacji wykonuje jeden taki przebieg oznaczania i odświeża siatkę (lub spiralę Ulama, która owija liczby 1…N na zewnątrz od środka) — liczby pierwsze są złote, a aktualnie przetwarzane p pomarańczowe. Drugi panel zestawia bieżącą funkcję liczącą liczby pierwsze π(x) — liczbę znalezionych dotąd liczb pierwszych — z klasycznym oszacowaniem x/ln(x), pozwalając obserwować, jak wraz ze wzrostem N ujawnia się twierdzenie o liczbach pierwszych.
🔬 Co pokazuje
Żywe sito logiczne na liczbach całkowitych od 2 do N (do 10 000): nieoznaczone liczby, które przetrwały, są pierwsze, a wielokrotności każdej nowo znalezionej liczby pierwszej p są skreślane począwszy od p² (mniejsze wielokrotności zostały już skreślone przez mniejsze liczby pierwsze). Wykres pod siatką porównuje rzeczywistą liczbę π(x) z x/ln(x) — asymptotycznym oszacowaniem z twierdzenia o liczbach pierwszych.
🎮 Jak korzystać
Przeciągnij suwak Limit N, aby wybrać, ile liczb całkowitych ma zostać przesianych, oraz Anim speed, aby ustawić liczbę kroków na klatkę. Przełączaj się między układem Grid a Ulam Spiral za pomocą przycisków widoku. Naciśnij Start, aby animować sito krok po kroku, Instant, aby rozwiązać je natychmiast, lub Reset, aby zbudować tablicę od nowa.
💡 Czy wiesz, że...
Sito musi testować kandydatów na liczby pierwsze p tylko do √N, a każdy z nich jest pomijany, jeśli został już oznaczony jako złożony przez mniejszą liczbę pierwszą — dlatego jego czas działania wynosi imponująco wydajne O(N log log N), co czyni je jednym z najszybszych znanych sposobów wyznaczania wszystkich liczb pierwszych poniżej danej granicy.
Najczęściej zadawane pytania
Dlaczego oznaczanie zaczyna się dopiero od p² zamiast od 2p?
Każda złożona wielokrotność p mniejsza niż p² — jak 2p, 3p, …, (p−1)p — ma już mniejszy czynnik pierwszy niż p, więc została skreślona podczas wcześniejszego przebiegu, gdy przetwarzana była ta mniejsza liczba pierwsza. Rozpoczynanie każdego przebiegu od p² pomija zbędną pracę i jest kluczową optymalizacją, która nadaje situ czas działania O(N log log N) zamiast wolniejszego O(N log N).
Jak spirala Ulama łączy się z tym sitem?
Widok spirali Ulama wykorzystuje dokładnie tę samą tablicę sita, co widok siatki, ale odrysowuje każdą ocalałą liczbę pierwszą wzdłuż kwadratowej spirali owijającej się na zewnątrz od środka, po jednej komórce na liczbę całkowitą. Wizualnie liczby pierwsze mają tendencję do grupowania się wzdłuż pewnych przekątnych linii w tym układzie — uderzający, wciąż nie do końca wyjaśniony wzór, po raz pierwszy zauważony przez matematyka Stanisława Ulama w 1963 roku, gdy bazgrolił podczas nudnego wykładu konferencyjnego.
Co oznacza wykres π(x) względem x/ln(x)?
π(x) to funkcja liczbowa liczb pierwszych: rzeczywista liczba liczb pierwszych mniejszych lub równych x, zliczana bezpośrednio w trakcie działania sita. x/ln(x) to wiodące asymptotyczne przybliżenie z twierdzenia o liczbach pierwszych (udowodnionego niezależnie przez Hadamarda i de la Vallée Poussina w 1896 roku). Obie krzywe zbliżają się do siebie coraz bardziej wraz ze wzrostem N, dokładnie tak, jak przewiduje twierdzenie — choć stosunek dąży do 1 dopiero w granicy x → ∞.
Dlaczego sito działa w czasie O(N log log N)?
Całkowita praca jest proporcjonalna do N razy suma 1/p po wszystkich liczbach pierwszych p ≤ √N (jedno „trafienie” na każdą wielokrotność każdej liczby pierwszej). Zgodnie z drugim twierdzeniem Mertensa suma odwrotności liczb pierwszych do danej granicy rośnie jak logarytm logarytmu tej granicy, więc całkowita praca skaluje się jak N·log log N — asymptotycznie bliskie liniowemu i znacznie szybsze niż próbne dzielenie każdej liczby z osobna.
Co śledzi statystyka największej luki między liczbami pierwszymi?
Podaje ona największą różnicę między kolejnymi znalezionymi liczbami pierwszymi aż do bieżącej granicy N (na przykład lukę 8 między 89 a 97). Luki między liczbami pierwszymi rosną nieregularnie, ale przeciętnie poszerzają się jak ln(N) wraz ze wzrostem N, zgodnie z twierdzeniem o liczbach pierwszych; nieudowodniona hipoteza Craméra proponuje ściślejsze ograniczenie na wielkość pojedynczej luki.
Czy to sito dowodzi lub obala hipotezę liczb bliźniaczych?
Nie — sito może wypisać każdą parę liczb bliźniaczych (p, p+2) poniżej wybranej granicy N, ale to potwierdza jedynie skończenie wiele przykładów. Hipoteza liczb pierwszych bliźniaczych zakłada istnienie nieskończenie wielu takich par wśród wszystkich liczb pierwszych, co pozostaje otwartym problemem teorii liczb mimo silnych dowodów numerycznych i częściowo teoretycznych (w tym przełomowego wyniku Zhanga z 2013 roku dotyczącego ograniczonych luk).