Sito Eratostenesa

Aby zapoznać się z rzeźbą, zobacz 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 jest starożytnym algorytmem znajdowania wszystkich liczb pierwszych do dowolnej granicy.

Czyni to poprzez iteracyjne oznaczanie jako złożone (tj. nie liczby pierwsze) wielokrotności każdej liczby pierwszej, zaczynając od pierwszej liczby pierwszej, 2. Wielokrotności danej liczby pierwszej są generowane jako ciąg liczb rozpoczynający się od tej liczby pierwszej, ze stałą różnicą między nimi , która jest równa tej liczbie pierwszej. Jest to kluczowa różnica między sitem a użyciem dzielenia próbnego do sekwencyjnego testowania każdej liczby kandydującej pod kątem podzielności przez każdą liczbę pierwszą. Gdy wszystkie wielokrotności każdej odkrytej liczby pierwszej zostaną oznaczone jako złożone, pozostałe nieoznaczone liczby są liczbami pierwszymi.

Najwcześniejsza znana wzmianka o sicie ( starogrecki : κόσκινον Ἐρατοσθένους , kóskinon Eratosthénous ) znajduje się we wprowadzeniu do arytmetyki Nikomachusa z Gerazy , na początku II wieku. Księga CE, która przypisuje ją Eratostenesowi z Cyreny , III wiek. p.n.e. grecki matematyk , choć opisał przesiewanie liczbami nieparzystymi, a nie liczbami pierwszymi.

Jedno z wielu sit liczb pierwszych , jest to jeden z najskuteczniejszych sposobów znajdowania wszystkich mniejszych liczb pierwszych. Może być używany do znajdowania liczb pierwszych w postępach arytmetycznych .

Przegląd




Przesiej dwójkę i przesiej trójkę: sito Eratostenesa. Kiedy wielokrotności wysublimują, Liczby, które pozostają, są liczbami pierwszymi.

Anonimowy

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

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

  1. Utwórz listę kolejnych liczb całkowitych od 2 do n : (2, 3, 4, ..., n ) .
  2. Na początku 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. Kiedy algorytm się kończy, wszystkie liczby, które nie są zaznaczone na liście, są liczbami pierwszymi poniżej n .

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

Dla doprecyzowania 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 p2 , że algorytm może zakończyć się w kroku 4, gdy jest większe niż n .

Innym udoskonaleniem jest początkowe wypisanie tylko liczb nieparzystych, (3, 5, ..., n ) i policzenie w przyrostach co 2 p w kroku 3, oznaczają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, tak aby tylko takie wielokrotności p są generowane, 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 co drugą liczbę na liście po 2, licząc od 2 w przyrostach 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ępną liczbą na liście po 2 jest 3; skreśl co trzecią liczbę na liście po 3, licząc od 3 w przyrostach 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ępną liczbą, która nie została jeszcze przekreślona na liście po 3, jest 5; skreślić co piątą liczbę na liście po 5, licząc od 5 w odstępach co 5 (tj. 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ępną liczbą, która nie została jeszcze przekreślona na liście po 5, jest 7; następnym krokiem byłoby skreślenie co siódmej 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 nie przekreślone w tym miejscu na liście 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: 

       
          algorytm  Sito Eratostenesa  wejście  : liczba całkowita  n  > 1.  wyjście  : wszystkie liczby pierwsze od 2  do  n  .  niech  A  będzie  tablicą wartości   logicznych  , indeksowanych przez  liczbę całkowitą  s 2 do  n  , początkowo wszystkie  ustawione  na  true  .  dla  i  = 2, 3, 4, ..., nieprzekraczające  √  n  wykonaj,  jeśli  A  [  i  ]  
              
                 

      jest  prawdziwe  dla  j  =  i  2  ,  i  2  +  i  ,  i  2  +2  i  ,  i  2  +3  i  , ..., nieprzekraczające  n  do  set  A  [  j  ] :=  false  zwraca  wszystkie  i  takie, że  A  [  i  ]  jest  prawdą  .

Algorytm ten 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ść czasowa tego algorytmu wynosi O ( n log log n ) , pod warunkiem, że aktualizacja tablicy jest operacją O (1) , jak to zwykle bywa.

Sito segmentowe

Jak zauważa Sorenson, problemem z sitem Eratostenesa nie jest liczba operacji, które wykonuje, ale raczej wymagania dotyczące pamięci. Dla dużych n zakres liczb pierwszych może nie mieścić się w pamięci; co gorsza, 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 jednocześnie przesiewana jest tylko część asortymentu. Są one znane od lat 70. XX wieku 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 następujących 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 Δ .
    2. Oznacz jako inne niż pierwsze pozycje w tablicy odpowiadające wielokrotnościom każdej liczby pierwszej p ≤ √ m znalezionej do tej pory, wyliczając jej wielokrotności w krokach p zaczynając od najniższej wielokrotności p między m - Δ a m .
    3. Pozostałe niezaznaczone pozycje w tablicy odpowiadają liczbom pierwszym w segmencie. Nie trzeba zaznaczać żadnych wielokrotności tych liczb pierwszych, ponieważ wszystkie te liczby pierwsze są większe niż √ m , jak dla k ≥ 1 , jeden ma .

Jeśli Δ zostanie 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 liczby pierwsze przesiewania poniżej √ n zgodnie z wymaganiami sita Eratostenesa podzielonego na segmenty nie mieszczą się w pamięci, zamiast tego można zastosować wolniejsze, ale znacznie bardziej zajmujące miejsce sito, takie jak sito Sorensona.

Sito przyrostowe

Przyrostowe sformułowanie sita generuje liczby pierwsze w nieskończoność (tj. bez górnej granicy) poprzez przeplatanie generowania 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 liczenie w górę od kwadratu liczby pierwszej w przyrostach p (lub 2 p dla nieparzystych liczb pierwszych). Generowanie należy rozpocząć dopiero po osiągnięciu kwadratu liczby pierwszej, aby uniknąć niekorzystnego wpływu na wydajność. Można to wyrazić symbolicznie w ramach przepływu danych jako 

 liczby pierwsze  = [  2  ,  3  , ...] \ [[  p  ²,  p  ²+  p  , ...] dla  p  w  liczbach pierwszych  ],

przy użyciu notacji ze zrozumieniem list z \ oznaczającym odejmowanie zbioru ciągów arytmetycznych liczb.

Liczby pierwsze można również wytwarzać przez iteracyjne odsiewanie kompozytów poprzez testowanie podzielności za pomocą kolejnych liczb pierwszych, po jednej liczbie pierwszej 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ą teoretyczną złożoność niż sito Eratostenesa w generowaniu zakresów liczb pierwszych.

Podczas testowania każdej liczby pierwszej optymalny algorytm dzielenia próbnego wykorzystuje wszystkie liczby pierwsze nieprzekraczające jej pierwiastka kwadratowego, podczas gdy sito Eratostenesa wytwarza każdy złożony tylko z jego czynników pierwszych i pobiera liczby pierwsze „za darmo” między złożonymi. Szeroko znany funkcjonalny kod sita Davida Turnera z 1975 r. Jest często przedstawiany jako przykład sita Eratostenesa, ale w rzeczywistości jest to nieoptymalne sito podziału próbnego.

Złożoność algorytmiczna

Sito Eratostenesa jest popularnym sposobem porównywania wydajności komputera. Złożoność czasowa obliczania wszystkich liczb pierwszych poniżej n w modelu maszyny o swobodnym dostępie to operacje O ( n log log n ) , co jest bezpośrednią konsekwencją faktu, że pierwszy szereg harmoniczny asymptotycznie zbliża się do log log n . Ma jednak wykładniczą złożoność czasową w odniesieniu do wielkości danych wejściowych, co czyni go pseudowielomianowym . Podstawowy algorytm wymaga O ( n ) pamięci.

Złożoność bitowa algorytmu wynosi O ( n (log n ) (log log n ) ) operacji bitowych z wymaganiami dotyczącymi pamięci O ( n ) .

Zwykle implementowana wersja z segmentacją stron ma taką samą złożoność operacyjną O ( n log log n ) jak wersja bez segmentacji, ale zmniejsza wymagania dotyczące miejsca do bardzo minimalnego rozmiaru strony segmentu oraz pamięci wymaganej do przechowywania podstawowych liczb pierwszych mniejszych niż pierwiastek kwadratowy z zakresu używanego do wybierania kompozytów z kolejnych segmentów strony o rozmiarze O ( √ n / log n ) .

Specjalna (rzadko, jeśli w ogóle, wdrażana) podzielona na segmenty wersja sita Eratostenesa, z podstawowymi optymalizacjami, wykorzystuje O ( n ) operacji i O ( √ n log log n / log n ) bitów pamięci.

Używanie notacji dużego O ignoruje stałe współczynniki i przesunięcia, które mogą być bardzo znaczące 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ć podzielony na strony, 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ż wymagało to podstawowe sito Eratostenesa z segmentacją stron wykorzystujące O ( √ n / log n ) bitów pamięci). Praca Pritcharda zmniejszyła zapotrzebowanie na pamięć kosztem dużego stałego współczynnika. Chociaż wynikowe sito kołowe ma wydajność O ( n ) i akceptowalne wymagania dotyczące pamięci, nie jest szybsze niż rozsądnie podstawowe sito Eratostenesa z faktoryzacją koła dla praktycznych zakresów przesiewania.

Sito Eulera

Eulera na formułę iloczynu zeta zawiera wersję sita Eratostenesa, w której każda liczba złożona jest eliminowana dokładnie raz. To samo sito zostało ponownie odkryte i zaobserwowane w czasie liniowym przez Griesa i Misrę (1978) . To też zaczyna się od listy liczb od 2 do n w celu. Na każdym kroku pierwszy element jest identyfikowany jako kolejna liczba pierwsza, jest mnożony przez każdy element listy (a więc zaczynając od siebie), a wyniki zaznaczane są na liście do późniejszego usunięcia. Początkowy element i zaznaczone elementy 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 pokazano przykład, 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 liczbami pierwszymi (por. faktoryzacja koła ), tak aby lista zaczynała się od następnej liczba pierwsza, a wszystkie liczby znajdujące się poniżej kwadratu pierwszego elementu również będą liczbami pierwszymi.

Zatem podczas generowania ograniczonej sekwencji liczb pierwszych, gdy następna zidentyfikowana liczba pierwsza przekracza pierwiastek kwadratowy z 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.

Zauważ, że liczby, które zostaną odrzucone w kroku, 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ż

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Sieve_of_Eratosthenes&oldid=1140779429 ”