Síto Eratosthenes - Sieve of Eratosthenes

Sieve of Eratosthenes: kroky algoritmu pro prvočísla pod 121 (včetně optimalizace začátku od čtverce primu).

V matematice je Eratosthenovo síto starověký algoritmus pro hledání všech prvočísel až do dané hranice.

Dělá to iterativním označením násobků každého prvočísla jako složeného (tj. Ne prvočísla), počínaje prvním prvočíslem, 2. Násobky daného prvočísla jsou generovány jako posloupnost čísel začínajících od tohoto prvočísla, s konstantním rozdílem mezi nimi se rovná té prvočísle. Toto je klíčové rozlišení síta od používání zkušebního dělení k postupnému testování dělitelnosti každého kandidátského čísla každým prvočíslem. Jakmile jsou všechny násobky každého objeveného prvočísla označeny jako kompozity, zbývající neoznačená čísla jsou prvočísla.

Nejdříve známý odkaz na síto ( starověká řečtina : κόσκινον Ἐρατοσθένους , kóskinon Eratosthénous ) je v Nicomachus of Gerasa 's Introduction to Arithmetic , rané 2. století. Kniha CE, která ji popisuje a připisuje Eratosthenesovi z Kyrény , 3. století. BCE řecký matematik .

Jeden z řady sít prvotních čísel je jedním z nejefektivnějších způsobů, jak najít všechny menší prvočísla. Může být použit k nalezení prvočísel v aritmetických postupech .

Přehled

Prosejte dvojku a prosejte trojku:
Síto Eratosthenes.
Když násobky vyniknou,
zůstanou čísla Prime.

Anonymní

Prvočíslo je přirozené číslo , které má přesně dva zřetelné přirozené číslo dělitele : číslo 1 a sám.

Chcete -li najít všechna prvočísla menší nebo rovná danému celému číslu $n$ Eratosthenesovou metodou:

Vytvořte seznam po sobě jdoucích celých čísel od 2 do $n$ : $(2, 3, 4, ..., n)$ .
Zpočátku nechť $p se$ rovná 2, nejmenší prvočíslo.
Vyčíslete násobky $p$ počítáním v krocích po $p$ od $2 p$ do $n$ a označte je v seznamu (budou to $2 p, 3 p, 4 p, ...$ ; $p$ samotné by nemělo být označeno).
Najděte nejmenší číslo v seznamu větší než $p,$ které není označeno. Pokud takové číslo nebylo, přestaňte. V opačném případě nechť se $p$ nyní rovná tomuto novému číslu (což je další prvočíslo) a opakujte od kroku 3.
Když algoritmus skončí, zbývající čísla, která nejsou v seznamu označena, jsou všechna prvočísla níže $n$ .

Hlavní myšlenkou je, že každá hodnota daná $p$ bude primární, protože pokud by byla složená, byla by označena jako násobek nějaké jiné, menší primární. Některá čísla mohou být označena vícekrát (např. 15 bude označeno jak pro 3, tak pro 5).

Pro upřesnění stačí označit čísla v kroku 3 počínaje od $p 2$ , protože všechny menší násobky $p$ již budou v tomto bodě označeny. To znamená, že algoritmu je povoleno ukončit v kroku 4, když $p 2$ je větší než $n$ .

Dalším zpřesněním je zpočátku vypsat pouze lichá čísla $((3, 5, ..., n))$ a počítat v krocích po $2 p$ od $p 2$ v kroku 3, čímž označíme pouze liché násobky $p$ . To se skutečně objevuje v původním algoritmu. To lze zobecnit pomocí faktorizace kol , která tvoří počáteční seznam pouze z čísel coprime s několika prvních prvočísel a ne pouze z pravděpodobností (tj. Čísel coprime s 2), a počítání v odpovídajícím způsobem upravených přírůstcích tak, že pouze takové násobky $p$ jsou generované, které jsou coprime s těmi malými prvočísly, na prvním místě.

Příklad

Chcete -li najít všechna prvočísla menší nebo rovna 30, postupujte následovně.

Nejprve vytvořte seznam celých čísel 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

První číslo v seznamu je 2; škrtněte každé 2. číslo v seznamu po 2 počítáním od 2 v přírůstcích po 2 (to budou všechny násobky 2 v seznamu):

 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

Další číslo v seznamu po 2 je 3; škrtněte každé 3. číslo v seznamu po 3 spočítáním od 3 v přírůstcích po 3 (to budou všechny násobky 3 v seznamu):

 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

Další číslo, které v seznamu po 3 ještě nebylo přeškrtnuto, je 5; přeškrtněte každé 5. číslo v seznamu po 5 tím, že budete počítat od 5 v krocích po 5 (tj. všechny násobky 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

Další číslo, které v seznamu po 5 ještě nebylo přeškrtnuto, je 7; dalším krokem by bylo vyškrtnout každé 7. číslo v seznamu po 7, ale všechna jsou v tomto bodě již přeškrtnuta, protože tato čísla (14, 21, 28) jsou také násobky menších prvočísel, protože 7 × 7 je větší než 30. Čísla, která nejsou v tomto bodě seznamu přeškrtnuta, jsou všechna prvočísla pod 30:

 2  3     5     7           11    13          17    19          23                29

Algoritmus a varianty

Pseudo kód

Síto Eratosthenes lze vyjádřit v pseudokódu následujícím způsobem:

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  $\sqrt n$  do
        if A[i] is true
            for j = i², i²+i, i²+2i, i²+3i, ..., not exceeding n do
                A[j] := false

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

Tento algoritmus produkuje všechna prvočísla ne větší než $n$ . Obsahuje běžnou optimalizaci, která má začít s výčtem násobků každé prvočísla $i$ od $i 2$ . Časová složitost tohoto algoritmu je $O (n log log n)$ , za předpokladu, že aktualizace pole je $O (1)$ operace, která je pro tento případ.

Segmentované síto

Jak Sorenson poznamenává, problémem síta Eratosthenes není počet operací, které provádí, ale spíše jeho paměťové nároky. U velkých $n$ se rozsah prvočísel nemusí vejít do paměti; horší, dokonce i pro mírné $n$ , je jeho použití mezipaměti vysoce neoptimální. Algoritmus prochází celým polem $A$ a nevykazuje téměř žádnou referenční lokalitu .

Řešení těchto problémů nabízejí segmentovaná síta, kde jsou současně prosety pouze části rozsahu. Ty jsou známy již od 70. let minulého století a fungují následovně:

Rozdělte rozsah 2 až $n$ na segmenty určité velikosti $Δ \leq \sqrt n$ .
Najděte prvočísla v prvním (tj. Nejnižším) segmentu pomocí pravidelného síta.
Pro každý z následujících segmentů ve vzestupném pořadí, kde m je nejvyšší hodnota segmentu, najděte v něm prvočísla takto:
1. Nastavte booleovské pole velikosti $Δ$ a
2. Označte jako neoznačené pozice v poli odpovídající násobkům každého dosud nalezeného prvočísla $p \leq \sqrt m, a to$ tak, že vypočítáte nejnižší násobek $p$ mezi $m - Δ$ a $m$ a výčty jeho násobků v krocích $p$ jako obvykle. Zbývající pozice odpovídají prvočíslům v segmentu, protože druhá mocnina prvočísla v segmentu není v segmentu (pro $k \geq 1$ má jeden ). ${\ Displaystyle (k \ Delta +1)^{2}> (k +1) \ Delta}$

Pokud je $Δ$ zvoleno jako $\sqrt n$ , prostorová složitost algoritmu je $O (\sqrt n)$ , zatímco časová složitost je stejná jako u pravidelného síta.

Pro rozsahy s horní hranicí $n$ tak velkou, že prosévání připraví pod $\sqrt n$ podle požadavků segmentového síta Eratosthenes se nevejde do paměti, lze místo toho použít pomalejší, ale mnohem prostorově efektivnější síto, jako je síto Sorenson .

Přírůstkové síto

Inkrementální formulace síta generuje prvočísla na neurčito (tj. Bez horní hranice) prokládáním generování prvočísel generováním jejich násobků (takže prvočísla lze nalézt v mezerách mezi násobky), kde násobky každého prvočísla $p$ jsou generovány přímo počítáním ze čtverce primární v krocích po $p$ (nebo $2 p$ pro liché prvočísla). Generování musí být zahájeno pouze při dosažení čtverce primu, aby se zabránilo nepříznivým účinkům na účinnost. Lze to vyjádřit symbolicky pod paradigmatem toku dat jako

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

použití seznamu s porozuměním notaci se \označuje nastavenou odčítání z aritmetická posloupnost čísel.

Prvočísla mohou být také vytvořena iterativním proséváním kompozitů testováním dělitelnosti sekvenčními prvočísly, vždy jednou primární. Není to Eratosthenovo síto, ale je s ním často zaměňováno, přestože Eratosthenovo síto místo vytváření kompozitů přímo generuje. Zkušební rozdělení má při generování rozsahů prvočísel horší teoretickou složitost než síto Eratosthenes.

Při testování každého prvočísla používá optimální zkušební dělící algoritmus všechna prvočísla nepřesahující jeho druhou odmocninu, zatímco síto Eratosthenes produkuje každý kompozit pouze z jeho hlavních faktorů a získává prvočísla „zdarma“ mezi kompozity. Široce známý kód funkčního síta z roku 1975 Davida Turnera je často uváděn jako příklad síta Eratosthenes, ale ve skutečnosti je suboptimálním sítem pro zkušební dělení.

Algoritmická složitost

Síto Eratosthenes je populární způsob, jak porovnávat výkon počítače. Časová složitost výpočtu všechna prvočísla dole $n$ v RAM stroj modelu je $O (n log log n)$ operací, je přímým důsledkem skutečnosti, že primární harmonická řada asymptoticky blíží $log log n$ . Má však exponenciální časovou složitost s ohledem na velikost vstupu, což z něj činí pseudopolynomiální algoritmus. Základní algoritmus vyžaduje $O (n)$ paměti.

Bit složitost algoritmu je $O (N (log n) (log log n)),$ bitové operace s požadavkem na paměti $O (n)$ .

Normálně implementovaná segmentovaná verze stránky má stejnou provozní složitost $O (n log log n)$ jako nesegmentovaná verze, ale snižuje nároky na prostor na velmi minimální velikost segmentové stránky plus paměť potřebnou k uložení základních prvočísel menší než druhá odmocnina rozsahu používaného k vyřazení kompozitů z po sobě jdoucích segmentů stránky velikosti $O (.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px} √ n/log č)$ .

Speciální (zřídka, pokud vůbec, implementovaná) segmentovaná verze síta Eratosthenes se základními optimalizacemi využívá operace $O (n)$ a $O (\sqrt n log protokol č / log č)$ kousky paměti.

Použití velké notace O ignoruje konstantní faktory a offsety, které mohou být pro praktické rozsahy velmi významné: Síto variace Eratosthenes známé jako Pritchardovo kolové síto má výkon $O (n)$ , ale jeho základní implementace vyžaduje buď algoritmus „jedno velké pole“ což omezuje jeho použitelný rozsah na množství dostupné paměti, jinak musí být segmentována stránka, aby se snížilo využití paměti. Při implementaci se segmentací stránky za účelem úspory paměti základní algoritmus stále vyžaduje asi $O (n / log č)$ bitů paměti (mnohem víc než požadavek základního segmentovaného síta Eratosthenes pomocí $O (\sqrt n / log č)$ kousky paměti). Pritchardova práce snížila požadavek na paměť za cenu velkého konstantního faktoru. Ačkoli výsledné kolové síto mávýkon $O (n)$ a přijatelný požadavek na paměť, není pro praktické rozsahy prosévání rychlejší než rozumně základní síto Eratosthenes Factorized Wheel Factorized.

Eulerovo síto

Eulerův důkaz vzorce produktu zeta obsahuje verzi síta Eratosthenes, ve kterém je každé složené číslo vyloučeno přesně jednou. Stejný síto byla nově objevená a pozorováno, že se lineární čas od Gries & Misra (1978) . Také to začíná seznamem čísel od 2 do $n$ v uvedeném pořadí. V každém kroku je první prvek identifikován jako další prvočíslo, je vynásoben každým prvkem seznamu (tedy začíná u sebe) a výsledky jsou označeny v seznamu pro následné odstranění. Počáteční prvek a označené prvky jsou poté odstraněny z pracovní sekvence a postup se opakuje:

 [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  ...
 [...]

Zde je ukázka ukázána počínaje od kurzů, po prvním kroku algoritmu. V $k$ -tom kroku jsou tedy ze seznamu odstraněny všechny zbývající násobky $k$ -té prvočísla, které poté budou obsahovat pouze čísla coprime s první $k$ prvočísly (srov. Faktorizace kola ), takže seznam začne dalším prvočíslo a všechna čísla v něm pod čtvercem jeho prvního prvku budou také prvočísla.

Když tedy při generování ohraničené posloupnosti prvočísel překročí druhá identifikovaná prvočísla druhou odmocninu horní hranice, všechna zbývající čísla v seznamu jsou prvočísla. Ve výše uvedeném příkladu je dosaženo identifikací 11 jako dalšího prvočísla, přičemž je uveden seznam všech prvočísel menších nebo rovných 80.

Všimněte si toho, že čísla, která budou vyřazena o krok, jsou stále používána při označování násobků v tomto kroku, např. Pro násobky 3 jsou 3 × 3 = 9 , 3 × 5 = 15 , 3 × 7 = 21 , 3 × 9 = 27 , ..., 3 × 15 = 45 , ..., takže s tím je třeba zacházet opatrně.

Viz také

Reference

externí odkazy

primesieve - Velmi rychlé vysoce optimalizované C/C ++ segmentované síto Eratosthenes
Eratosthenes, síto v encyklopedii matematiky
Interaktivní stránka JavaScript
Síto Eratosthenes od George Becka, Wolfram Demonstrations Project .
Síto Eratosthenes v Haskellu
Algoritmus Eratosthenesova síta ilustrovaný a vysvětlený. Implementace Java a C ++.
Související síto napsané v jazyce sestavení x86
Rychle optimalizované vysoce paralelní CUDA segmentované síto Eratosthenes v C
SieveOfEratosthenesInManyProgrammingLanguages c2 wiki stránka
The Art of Prime Sieving Sieve of Eratosthenes in C z roku 1998 s pěknými funkcemi a vysvětlenými algoritmickými triky.

Languages

In other projects