Sito Eratostenesa - Sieve of Eratosthenes

Rzeźba znajduje się w Sito Eratostenesa (rzeźba) .
Sito Eratostenesa: kroki algorytmu dla liczb pierwszych poniżej 121 (w tym optymalizacja rozpoczynania od kwadratu liczby pierwszej).

W matematyce , Sito Eratostenesa to starożytna algorytm znajdowania wszystkich liczb pierwszych do danego limitu.

Czyni to poprzez iteracyjne oznaczenie jako złożone (tj. nie pierwsze) wielokrotności każdej liczby pierwszej, zaczynając od pierwszej liczby pierwszej, 2. Wielokrotności danej liczby pierwszej są generowane jako sekwencja liczb zaczynając od tej liczby pierwszej, ze stałą różnicą między nimi, która jest równa tej liczbie pierwszej. Jest to kluczowe odróżnienie sita od używania dzielenia próbnego do sekwencyjnego testowania każdej liczby kandydującej pod kątem podzielności przez każdą pierwszą. Gdy wszystkie wielokrotności każdej odkrytej liczby pierwszej zostały oznaczone jako złożone, pozostałe nieoznaczone liczby są liczbami pierwszymi.

Najwcześniejszym znanym odniesieniem do sita ( starożytnego greckiego : κόσκινον Ἐρατοσθένους , kóskinon Eratosthénous ) jest Nikomachus z Gerasie „s Wprowadzenie arytmetyczną , wczesne 2 procent. Księga CE, która go opisuje i przypisuje Eratostenesowi z Cyreny , III wiek. Pne grecki matematyk .

Jedno z wielu sit liczb pierwszych , jest to jeden z najbardziej wydajnych sposobów znajdowania wszystkich mniejszych liczb pierwszych. Może być używany do znajdowania liczb pierwszych w ciągach arytmetycznych .

Przegląd

Przesiać dwójkę i przesiać trójkę:
sito Eratostenesa.
Kiedy wielokrotności wzniosą się,
Liczby, które pozostają, są Pierwsze.

Anonimowy

Liczba pierwsza to liczba naturalna, która ma dokładnie dwa różne dzielniki liczb naturalnych : liczbę 1 i samą siebie.

Aby znaleźć wszystkie liczby pierwsze mniejsze lub równe danej liczbie całkowitej n metodą Eratostenesa:

  1. Utwórz listę kolejnych liczb całkowitych od 2 do n : (2, 3, 4, ..., n ) .
  2. Początkowo niech p będzie równe 2, najmniejszej liczbie pierwszej.
  3. Wylicz wielokrotności p , licząc w przyrostach p od 2 p do n i zaznacz je na liście (będą to 2 p , 3 p , 4 p , ... ; samego p nie należy zaznaczać).
  4. Znajdź najmniejszą liczbę na liście większą niż p, która nie jest zaznaczona. Jeśli nie było takiego numeru, przestań. W przeciwnym razie niech p będzie teraz równe tej nowej liczbie (która jest następną liczbą pierwszą) i powtórz od kroku 3.
  5. Gdy algorytm się kończy, liczby pozostałe nie zaznaczone na liście to wszystkie liczby pierwsze poniżej n .

Główną ideą jest tutaj to, że każda wartość podana p będzie liczbą pierwszą, ponieważ gdyby była złożona, byłaby oznaczona jako wielokrotność jakiejś innej, mniejszej liczby pierwszej. Zwróć uwagę, że niektóre liczby mogą być zaznaczone więcej niż jeden raz (np. 15 będzie zaznaczonych zarówno dla 3, jak i 5).

Jako uściślenie wystarczy zaznaczyć liczby w kroku 3 zaczynając od p 2 , ponieważ wszystkie mniejsze wielokrotności p będą już zaznaczone w tym miejscu. Oznacza to, że algorytm może zakończyć się w kroku 4, gdy p 2 jest większe niż n .

Innym udoskonaleniem jest początkowe wymienienie tylko liczb nieparzystych (3, 5, ..., n ) i liczenie w odstępach co 2 p od p 2 w kroku 3, zaznaczając w ten sposób tylko nieparzyste wielokrotności p . To faktycznie pojawia się w oryginalnym algorytmie. Można to uogólnić za pomocą faktoryzacji koła , tworząc początkową listę tylko z liczb względnie pierwszych z kilkoma pierwszymi liczbami pierwszymi, a nie tylko z szans (tj. liczb względnie pierwszych z 2), i licząc w odpowiednio dostosowanych przyrostach, aby tylko takie wielokrotności p były wygenerowane, które są względnie pierwsze z tymi małymi liczbami pierwszymi.

Przykład

Aby znaleźć wszystkie liczby pierwsze mniejsze lub równe 30, wykonaj następujące czynności.

Najpierw wygeneruj listę liczb całkowitych od 2 do 30: 

 2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Pierwsza liczba na liście to 2; wykreśl każdą drugą liczbę na liście po 2, licząc od 2 w odstępach co 2 (będą to wszystkie wielokrotności 2 na liście): 

 2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Następna liczba na liście po 2 to 3; wykreśl każdą trzecią liczbę na liście po 3, licząc od 3 w odstępach co 3 (będą to wszystkie wielokrotności 3 na liście): 

 2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Następna liczba, która nie została jeszcze skreślona na liście po 3, to 5; wykreśl każdą piątą liczbę na liście po 5, licząc od 5 w odstępach co 5 (tzn. wszystkie wielokrotności 5): 

 2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Następna liczba, która nie została jeszcze skreślona na liście po 5, to 7; następnym krokiem byłoby wykreślenie każdej 7 liczby na liście po 7, ale wszystkie są już przekreślone w tym momencie, ponieważ te liczby (14, 21, 28) są również wielokrotnościami mniejszych liczb pierwszych, ponieważ 7 × 7 jest większe niż 30. Liczby nieskreślone w tym miejscu listy to wszystkie liczby pierwsze poniżej 30: 

 2  3     5     7           11    13          17    19          23                29

Algorytm i warianty

Pseudo kod

Sito Eratostenesa można wyrazić w pseudokodzie w następujący sposób: 

algorithm Sieve of Eratosthenes is
    input: an integer n > 1.
    output: all prime numbers from 2 through n.

    let A be an array of Boolean values, indexed by integers 2 to n,
    initially all set to true.
    
    for i = 2, 3, 4, ..., not exceeding √n do
        if A[i] is true
            for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n do
                A[j] := false

    return all i such that A[i] is true.

Ten algorytm generuje wszystkie liczby pierwsze nie większe niż n . Zawiera wspólną optymalizację, która polega na rozpoczęciu wyliczania wielokrotności każdej liczby pierwszej i od i 2 . Złożoność tego algorytmu jest O ( n Log n ) , pod warunkiem, że zmiana tablicy jest O (1), działanie, jak to zwykle ma miejsce.

Sito segmentowe

Jak zauważa Sorenson, problem z sitem Eratostenesa nie polega na liczbie wykonywanych przez nie operacji, ale raczej na wymaganiach dotyczących pamięci. Dla large n zakres liczb pierwszych może nie mieścić się w pamięci; gorzej, nawet dla umiarkowanego n , jego użycie pamięci podręcznej jest wysoce nieoptymalne. Algorytm przechodzi przez całą tablicę A , nie wykazując prawie żadnej lokalizacji odniesienia .

Rozwiązaniem tych problemów są sita segmentowe , w których na raz przesiewa się tylko części asortymentu. Są one znane od lat 70. i działają w następujący sposób:

  1. Podziel zakres od 2 do n na segmenty o pewnym rozmiarze Δ ≤ √ n .
  2. Znajdź liczby pierwsze w pierwszym (tj. najniższym) segmencie, używając zwykłego sita.
  3. Dla każdego z poniższych segmentów, w porządku rosnącym, gdzie m jest najwyższą wartością segmentu, znajdź w nim liczby pierwsze w następujący sposób:
    1. Skonfiguruj tablicę logiczną o rozmiarze Δ i
    2. Oznacz jako inne niż pierwsze pozycje w tablicy odpowiadające wielokrotnościom każdej liczby pierwszej p ≤ √ m znalezionej do tej pory, obliczając najniższą wielokrotność p między m - Δ i m i wyliczając jej wielokrotności w krokach p jak zwykle. Pozostałe pozycje odpowiadają liczbom pierwszym w segmencie, ponieważ kwadrat liczby pierwszej w segmencie nie znajduje się w segmencie (dla k ≥ 1 , mamy ).

Jeśli Δ jest wybrane jako √ n , złożoność przestrzenna algorytmu wynosi O ( √ n ) , podczas gdy złożoność czasowa jest taka sama jak w przypadku zwykłego sita.

W przypadku zakresów z górną granicą n tak dużych, że przesiewanie wartości pierwszych poniżej √ n wymaganych przez podzielone na strony sito Eratostenesa nie może zmieścić się w pamięci, można zamiast tego użyć wolniejszego, ale znacznie bardziej wydajnego pod względem przestrzeni sita, takiego jak sito Sorensona .

Sito przyrostowe

Przyrostowa formuła sita generuje liczby pierwsze w nieskończoność (tj. bez górnej granicy) przeplatając generowanie liczb pierwszych z generowaniem ich wielokrotności (tak, że liczby pierwsze można znaleźć w przerwach między wielokrotnościami), gdzie wielokrotności każdej liczby pierwszej p są generowane bezpośrednio przez odliczanie od kwadratu liczby pierwszej w przyrostach p (lub 2 p dla nieparzystych liczb pierwszych). Generowanie musi być rozpoczęte dopiero po osiągnięciu kwadratu liczby pierwszej, aby uniknąć niekorzystnego wpływu na wydajność. Można to wyrazić symbolicznie w paradygmacie przepływu danych jako 

primes = [2, 3, ...] \ [[p², p²+p, ...] for p in primes],

stosując listowych notacji z \oznaczający zestaw odejmowanie z ciąg arytmetyczny liczb.

Pierwsze mogą być również wytwarzane przez iteracyjne przesiewanie kompozytów poprzez testowanie podzielności przez kolejne liczby pierwsze, jeden na raz. Nie jest to sito Eratostenesa, ale często jest z nim mylone, mimo że sito Eratostenesa bezpośrednio generuje kompozyty zamiast je testować. Podział próbny ma gorszą złożoność teoretyczną niż sito Eratostenesa w generowaniu zakresów liczb pierwszych.

Podczas testowania każdej liczby pierwszej optymalny algorytm dzielenia prób wykorzystuje wszystkie liczby pierwsze nieprzekraczające ich pierwiastka kwadratowego, podczas gdy sito Eratostenesa wytwarza każdy kompozyt tylko z jego czynników pierwszych i uzyskuje liczby pierwsze „za darmo” między kompozytami. Powszechnie znany kod funkcjonalnego sita z 1975 r. autorstwa Davida Turnera jest często przedstawiany jako przykład sita Eratostenesa, ale w rzeczywistości jest to nieoptymalne próbne sito dzielące.

Złożoność algorytmiczna

Sito Eratostenesa to popularny sposób na porównywanie wydajności komputera. Złożoność czas obliczania wszystkie liczby pierwsze poniżej n na maszynie o dostępie swobodnym modelu wynosi O ( n log log n ) operacji, bezpośrednią konsekwencją faktu, że główny szereg harmoniczny asymptotycznie zbliża log log n . Ma jednak wykładniczą złożoność czasową w odniesieniu do rozmiaru danych wejściowych, co czyni go algorytmem pseudowielomianowym . Podstawowy algorytm wymaga O ( n ) pamięci.

Nieco złożoność algorytmu jest O ( N (log n ) (Log n ) ) bit operacji z wymogiem pamięci O ( n ) .

Normalnie zaimplementowana wersja z segmentacją stron ma taką samą złożoność operacyjną O ( n log log n ) jak wersja niesegmentowana, ale zmniejsza wymagania dotyczące miejsca do bardzo minimalnego rozmiaru strony segmentu plus pamięć wymagana do przechowywania podstawowych liczb pierwszych mniej niż pierwiastek kwadratowy z zakresu użytego do usunięcia kompozytów z kolejnych segmentów strony o rozmiarze O ( √ n/log n) .

Specjalna (rzadko, jeśli w ogóle zaimplementowana) wersja segmentowa sita Eratostenesa, z podstawowymi optymalizacjami, wykorzystuje operacje O ( n ) i O ( √ ndziennik dziennika n/log n) bity pamięci.

Użycie notacji dużego O ignoruje stałe czynniki i przesunięcia, które mogą być bardzo istotne dla praktycznych zakresów: Sito odmiany Eratostenesa znane jako sito kołowe Pritcharda ma wydajność O ( n ) , ale jego podstawowa implementacja wymaga algorytmu „jednej dużej tablicy” co ogranicza jego użyteczny zakres do ilości dostępnej pamięci, w przeciwnym razie musi zostać podzielona na segmenty stron, aby zmniejszyć zużycie pamięci. Po zaimplementowaniu z segmentacją stron w celu zaoszczędzenia pamięci, podstawowy algorytm nadal wymaga około O (n/log n) bitów pamięci (znacznie więcej niż wymaganie podstawowego segmentowego sita Eratostenesa przy użyciu O (√ n/log n) bity pamięci). Praca Pritcharda zmniejszyła zapotrzebowanie na pamięć kosztem dużego współczynnika stałego. Chociaż powstałe sito kołowe mawydajność O ( n )i akceptowalną wymaganą pamięć, nie jest szybsze niż rozsądnie podstawowe sito Eratostenesa ze współczynnikiem kołowym dla praktycznych zakresów przesiewania.

Sito Eulera

Dowód Eulera formuły produktu zeta zawiera wersję sita Eratostenesa, w którym każda liczba złożona jest eliminowana dokładnie raz. To samo sito został odnaleziony i zaobserwowano dla liniowego czasu przez Gries i Misra (1978) . To również zaczyna się od listy liczb od 2 do n w kolejności. Na każdym kroku pierwszy element jest identyfikowany jako następny pierwszy, jest mnożony przez każdy element listy (a więc zaczynając od siebie), a wyniki są zaznaczane na liście do późniejszego usunięcia. Element początkowy i elementy zaznaczone są następnie usuwane z sekwencji roboczej, a proces jest powtarzany: 

 [2] (3) 5  7  9  11  13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79  ...
 [3]    (5) 7     11  13    17 19    23 25    29 31    35 37    41 43    47 49    53 55    59 61    65 67    71 73    77 79  ...
 [4]       (7)    11  13    17 19    23       29 31       37    41 43    47 49    53       59 61       67    71 73    77 79  ...
 [5]             (11) 13    17 19    23       29 31       37    41 43    47       53       59 61       67    71 73       79  ...
 [...]

Tutaj przykład jest pokazany zaczynając od kursów, po pierwszym kroku algorytmu. Tak więc na k- tym kroku wszystkie pozostałe wielokrotności k- tej liczby pierwszej są usuwane z listy, która odtąd będzie zawierała tylko liczby względnie pierwsze z pierwszymi k liczb pierwszych (por. faktoryzacja koła ), tak aby lista zaczynała się od następnego pierwszą, a wszystkie liczby znajdujące się w nim poniżej kwadratu pierwszego elementu również będą pierwsze.

Tak więc, podczas generowania ograniczonej sekwencji liczb pierwszych, gdy następna zidentyfikowana liczba pierwsza przekracza pierwiastek kwadratowy górnej granicy, wszystkie pozostałe liczby na liście są liczbami pierwszymi. W powyższym przykładzie osiąga się to po zidentyfikowaniu 11 jako następnej liczby pierwszej, dając listę wszystkich liczb pierwszych mniejszych lub równych 80.

Zwróć uwagę, że liczby, które zostaną odrzucone przez krok, są nadal używane podczas oznaczania wielokrotności w tym kroku, np. dla wielokrotności 3 jest to 3 × 3 = 9 , 3 × 5 = 15 , 3 × 7 = 21 , 3 × 9 = 27 , ..., 3 × 15 = 45 , ..., więc należy zachować ostrożność.

Zobacz też

Bibliografia

Zewnętrzne linki