Sieves Eratosthenesa: Znajdowanie Wszystkich Liczb Pierwszych Bez Podzielenia

Wycieranie wielokrotności, zachowywanie reszty

Sieve of Eratosthenes, zaproponowany przez greckiego matematyka około roku 240 p.n.e., znajduje wszystkie liczby pierwsze do ograniczenia N bez testowania podzielności dla każdego kandydata na liczbę pierwszą jedno po drugim. Zamiast tego pisze wszystkie liczby całkowite od 2 do N, a następnie wielokrotnie wycina najmniejszą liczbę nie wczytaną jeszcze i wycina wszystkie jej wielokrotności. To, co przeżywa całą rundę — tzn., która nie została wycięta — jest pierwsza, zgodnie z konstrukcją: liczba złożona zawsze ma najmniejszy czynnik pierwszy, a jego własny przeglad gwarantuje, że ją złapie.

dla p od 2 do N: jeśli p nie jest oznaczony: # p przeżył każdą wcześniejszą rundę → pierwsza dla wielokrotności m = p*p, p*p+p, p*p+2p, ... ≤ N: oznacz m jako złożone # wszystko nieoznaczone jest pierwsze Jedynym istotnym uproszczeniem jest rozpoczęcie każdej rundy od p² zamiast 2p. Każda liczba złożona mniejsza niż p², która jest wielokrotnością p, musi również być wielokrotnością pewnej liczby pierwszej mniejszej niż p, więc została już wycięta wcześniejszą rundą — rozpoczęcie od p² unika powtarzalnego pracy bez przegubu czegoś.

for p from 2 to N:
    if p is not marked:            # p survived every earlier sweep → prime
        for multiple m = p*p, p*p+p, p*p+2p, ... ≤ N:
            mark m as composite
# everything unmarked is prime

Dlaczego zatrzymuje się przy √N

Potrzebujesz sprawdzać tylko liczbami pierwszymi do √N. Każda liczba złożona m ≤ N ma przynajmniej jeden czynnik ≤ √m ≤ √N, więc jeśli m przetrwało każdy przebieg przez liczbę pierwszą do √N, to nie może być złożoną liczbą — musi być liczbą pierwszą. To jedno stwierdzenie zmienia skanowanie O(N) „liczb do sprawdzenia” na O(√N), a to jest całą przyczyną szybkości szkieletu: dla N = 10 000 potrzebujesz sprawdzić tylko 25 liczb pierwszych do 100.

Złożoność: lepsza niż testowanie każdego numeru osobno

Dzielenie spróbą na każdy numer od 1 do N kosztuje około O(N√N). Zamiast tego, sito wykorzystuje O(N log log N) pracy w sumie — dla każdego pierwszego p do √N oznacza około N/p wielokrotności, a suma 1/2 + 1/3 + 1/5 + 1/7 + ... nad pierwszymi zbiega (bardzo wolno) do log log N według drugiej tezy Mertensa. W praktyce to oznacza, że sito znajduje wszystkie liczby pierwsze poniżej dziesięci miliona w ułamku sekundy, czego próbne dzielenie nigdy nie dokona na taką szybkość.

work ≈ N · ( sum of 1/p for primes p ≤ √N )
        ≈ N · log(log(√N))
        =  O(N log log N)

Przelicznik pierwszych liczb i funkcja π(x)

Po wykonaniu siatki, dwie pytania stają się proste do rozpatrzenia wizualnie. Funkcja π(x), czyli przelicznik pierwszych liczb, po prostu liczy ile jest pierwszych liczb ≤ x — czytamy to bezpośrednio z pól przetrwanych przez siatkę. Twierdzenie o liczbach pierwszych mówi, że dla dużych x funkcja π(x) jest przybliżonie równa x / ln(x), co oznacza, że pierwsze liczby blisko x są na średnim odstępem około ln(x) — mniej i mniej gęste im dalej patrzymy, choć zawsze istnieje nieskończenie wiele (fakt udowodniony przez Euklidesa w kontraposycji ponad dwie tysiące lat temu). Przestrzenie między kolejnymi liczbami pierwszymi — odstęp między sąsiednimi liczbami pierwszymi — to, co siatka sprawia, że jest widoczne wizualnie: krótkie na początku (2, 3, 5, 7 są bardzo gęste), rozciągające się średnio, ale bez znanej największej przestrzeni i z okazjonalnymi dramatycznymi wyjatkami.

Optymalizacja za pomocą koła czynników: szybsze szkieletowanie

Proste dalsze przyspieszenie polega na całkowitej pominięciu liczb parzystych — poza 2, żadna liczba parzysta nie jest pierwsza, więc szkielet może przydzielać pamięć tylko dla liczb nieparzystych i zmniejszyć obydwie pamięć oraz pracę o połowę. Rozszerzenie tej samej idei do pominięcia wielokrotności 2, 3 i 5 ("koła" z okresem 30) usuwa około 73% liczb złożonych przed even siecem nawet nie begnie, co kosztuje lekko bardziej skomplikowaną schemat indeksacji. Podzielne szkieletowanie — przetwarzanie N w blokach pasujących do bufora pamięci — to drugie standardowe techniczne rozwiązanie, pozwalające algorhythmu skalować do miliardów bez wykorzystania wszystkich dostępnej pamięci.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Sieve of Eratosthenes — Animated Prime Number Finder i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.