Sieb von Eratosthenes - Sieve of Eratosthenes

Sieb von Eratosthenes: Algorithmusschritte für Primzahlen unter 121 (einschließlich Optimierung des Starts vom Primzahlquadrat).

In der Mathematik ist das Sieb des Eratosthenes ein alter Algorithmus, um alle Primzahlen bis zu einem bestimmten Grenzwert zu finden.

Es tut dies, indem es die Vielfachen jeder Primzahl iterativ als zusammengesetzt (dh nicht prim) markiert , beginnend mit der ersten Primzahl 2. Die Vielfachen einer gegebenen Primzahl werden als Folge von Zahlen ausgehend von dieser Primzahl mit konstanter Differenz erzeugt zwischen ihnen , die gleich dieser Primzahl ist. Dies ist der Hauptunterschied des Siebes gegenüber der Versuchsdivision , um jede Kandidatenzahl sequentiell auf Teilbarkeit durch jede Primzahl zu testen. Sobald alle Vielfachen jeder entdeckten Primzahl als Komposite markiert wurden, sind die verbleibenden unmarkierten Zahlen Primzahlen.

Die früheste bekannte Hinweis auf das Sieb ( Altgriechisch : κόσκινον Ἐρατοσθένους , kóskinon Eratosthénous ) ist in Nikomachos von Gerasa ‚s Einführung in die Arithmetik , einem frühen 2. Jh. CE-Buch, das es beschreibt und Eratosthenes von Kyrene zuschreibt , ein 3. Jh. v. BCE griechischer Mathematiker .

Als eines von mehreren Primzahlensieben ist es eine der effizientesten Möglichkeiten, alle kleineren Primzahlen zu finden. Es kann verwendet werden, um Primzahlen in arithmetischen Folgen zu finden .

Überblick

Sift the Two's and Sift the Three's:
Das Sieb des Eratosthenes.
Wenn die Vielfachen erhaben sind,
sind die verbleibenden Zahlen Primzahlen.

Anonym

Eine Primzahl ist eine natürliche Zahl , die genau zwei verschiedene natürliche Zahlenteiler hat : die Zahl 1 und sich selbst.

So finden Sie alle Primzahlen kleiner oder gleich einer gegebenen ganzen Zahl n nach der Methode von Eratosthenes:

  1. Erstellen Sie eine Liste aufeinanderfolgender Ganzzahlen von 2 bis n : (2, 3, 4, ..., n ) .
  2. Sei zunächst p gleich 2, der kleinsten Primzahl.
  3. Zählen Sie die Vielfachen von p auf, indem Sie in Schritten von p von 2 p bis n zählen , und markieren Sie sie in der Liste (dies sind 2 p , 3 p , 4 p , ... ; das p selbst sollte nicht markiert werden).
  4. Suchen Sie die kleinste Zahl in der Liste größer als p , die nicht markiert ist. Wenn es keine solche Nummer gab, stoppen Sie. Andernfalls sei p jetzt gleich dieser neuen Zahl (die die nächste Primzahl ist) und wiederhole ab Schritt 3.
  5. Wenn der Algorithmus endet, sind die verbleibenden Zahlen, die nicht in der Liste markiert sind, alle Primzahlen unter n .

Die Hauptidee dabei ist, dass jeder Wert, der p gegeben wird, eine Primzahl ist, denn wenn er zusammengesetzt wäre, würde er als Vielfaches einer anderen, kleineren Primzahl markiert. Beachten Sie, dass einige der Zahlen mehrmals markiert werden können (zB 15 wird sowohl für 3 als auch für 5 markiert).

Als Verfeinerung reicht es aus, die Zahlen in Schritt 3 ab p 2 zu markieren , da zu diesem Zeitpunkt bereits alle kleineren Vielfachen von p markiert sind. Dies bedeutet, dass der Algorithmus in Schritt 4 terminieren darf, wenn p 2 größer als n ist .

Eine andere Verfeinerung besteht darin, anfänglich nur ungerade Zahlen (3, 5, ..., n ) aufzulisten und in Schritt 3 in Inkrementen von 2 p von p 2 zu zählen, wodurch nur ungerade Vielfache von p markiert werden . Dies erscheint tatsächlich im ursprünglichen Algorithmus. Dies kann mit verallgemeinern Rad Faktorisierung , nur die erste Liste bilden , von Zahlen teilerfremd mit den ersten paar Primzahlen und nicht nur von Odds (dh Zahlen teilerfremd mit 2), und der Zählung in den entsprechend eingestellten Inkrementen so dass nur solche ein Vielfach von p ist , erzeugt, die mit diesen kleinen Primzahlen in erster Linie coprime sind.

Beispiel

Um alle Primzahlen kleiner oder gleich 30 zu finden, gehen Sie wie folgt vor.

Erstellen Sie zunächst eine Liste mit ganzen Zahlen von 2 bis 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

Die erste Zahl in der Liste ist 2; streichen Sie jede zweite Zahl in der Liste nach 2 durch, indem Sie von 2 in Schritten von 2 aufwärts zählen (dies sind alle Vielfachen von 2 in der Liste):

 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

Die nächste Zahl in der Liste nach 2 ist 3; streichen Sie jede dritte Zahl in der Liste nach 3 durch, indem Sie von 3 in Schritten von 3 aufwärts zählen (dies sind alle Vielfachen von 3 in der Liste):

 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

Die nächste noch nicht durchgestrichene Zahl nach 3 ist 5; streichen Sie jede 5. Zahl in der Liste nach 5 durch, indem Sie von 5 in Schritten von 5 aufwärts zählen (dh alle Vielfachen von 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

Die nächste noch nicht durchgestrichene Zahl nach 5 ist 7; der nächste Schritt wäre, jede 7. Zahl in der Liste nach 7 durchzustreichen, aber sie sind an dieser Stelle bereits alle durchgestrichen, da diese Zahlen (14, 21, 28) auch Vielfache kleinerer Primzahlen sind, weil 7 × 7 größer ist als 30. Die an dieser Stelle in der Liste nicht durchgestrichenen Zahlen sind alle Primzahlen unter 30:

 2  3     5     7           11    13          17    19          23                29

Algorithmus und Varianten

Pseudocode

Das Sieb von Eratosthenes kann wie folgt in Pseudocode ausgedrückt werden:

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.

Dieser Algorithmus erzeugt alle Primzahlen nicht größer als n . Es enthält eine allgemeine Optimierung, die darin besteht, die Vielfachen jeder Primzahl i von i 2 aufzuzählen . Die Zeitkomplexität dieses Algorithmus ist O ( n log log n ) , vorausgesetzt, die Array-Aktualisierung ist eine O (1) -Operation, wie es normalerweise der Fall ist.

Segmentsieb

Wie Sorenson feststellt, ist das Problem mit dem Sieb von Eratosthenes nicht die Anzahl der Operationen, die es ausführt, sondern der Speicherbedarf. Für große n passt der Bereich der Primzahlen möglicherweise nicht in den Speicher; schlimmer noch, selbst für moderate n ist die Cache- Nutzung höchst suboptimal. Der Algorithmus durchläuft das gesamte Array A und weist fast keine Referenzlokalität auf .

Eine Lösung dieser Probleme wird durch angeboten segmentierten Siebe, wo nur Teile des Bereichs werden in einer Zeit , gesiebt. Diese sind seit den 1970er Jahren bekannt und funktionieren wie folgt:

  1. Teilen Sie den Bereich 2 bis n in Segmente einer bestimmten Größe Δ ≤ n auf .
  2. Finden Sie die Primzahlen im ersten (dh im untersten) Segment, indem Sie das normale Sieb verwenden.
  3. Finden Sie für jedes der folgenden Segmente in aufsteigender Reihenfolge, wobei m der höchste Wert des Segments ist, die Primzahlen darin wie folgt:
    1. Richten Sie ein boolesches Array der Größe Δ ein und
    2. Mark als nicht-Prime die Positionen in dem Array entsprechend das Vielfachen von jedem Primzahl pm gefunden bisher, indem die niedrigste Vielfache von Berechnung p zwischen m - Δ und m und seine Vielfachen in Schritten von Aufzählen p wie üblich. Die restlichen Positionen entsprechen den Primzahlen im Segment, da das Quadrat einer Primzahl im Segment nicht im Segment liegt (für k ≥ 1 hat man ).

Wenn Δ gewählt wird n , die Platzkomplexität des Algorithmus ist O ( n ) , während die Zeitkomplexität der gleiche wie der der regulären Siebes.

Für Bereiche mit oberer Grenze n so groß, dass die Siebprimer unter n, wie es das seitensegmentierte Sieb von Eratosthenes erfordert, nicht in den Speicher passen, kann stattdessen ein langsameres, aber viel platzsparenderes Sieb wie das Sieb von Sorenson verwendet werden.

Inkrementalsieb

Eine inkrementelle Formulierung des Siebes erzeugt Primzahlen auf unbestimmte Zeit (dh ohne obere Schranke), indem die Generierung von Primzahlen mit der Generierung ihrer Vielfachen verschachtelt wird (so dass Primzahlen in Lücken zwischen den Vielfachen gefunden werden können), wobei die Vielfachen jeder Primzahl p werden direkt durch Aufwärtszählen vom Quadrat der Primzahl in Inkrementen von p erzeugt (oder 2 p für ungerade Primzahlen). Die Generierung darf erst bei Erreichen des Primzahlquadrats eingeleitet werden, um nachteilige Auswirkungen auf die Effizienz zu vermeiden. Es kann unter dem Datenflussparadigma symbolisch ausgedrückt werden als

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

Verwendung der Listenverständnisnotation mit der \Angabe von Mengensubtraktion von arithmetischen Zahlenfolgen.

Primes können auch durch iteratives Aussieben der Komposite durch Teilbarkeitstests durch aufeinanderfolgende Primes erzeugt werden, eine Prime nach der anderen. Es ist nicht das Sieb von Eratosthenes, wird aber oft damit verwechselt, obwohl das Sieb von Eratosthenes die Verbundstoffe direkt erzeugt, anstatt sie zu testen. Die Versuchsteilung hat eine größere theoretische Komplexität als das Sieb des Eratosthenes bei der Erzeugung von Primzahlenbereichen.

Beim Testen jeder Primzahl verwendet der optimale Probeteilungsalgorithmus alle Primzahlen, die ihre Quadratwurzel nicht überschreiten, während das Sieb von Eratosthenes jede Zusammensetzung nur aus ihren Primfaktoren erzeugt und die Primzahlen "umsonst" zwischen den Zusammensetzungen erhält. Der weithin bekannte funktionale Siebcode von 1975 von David Turner wird oft als Beispiel für das Sieb von Eratosthenes präsentiert, ist aber eigentlich ein suboptimales Versuchsteilungssieb.

Algorithmische Komplexität

Das Sieb von Eratosthenes ist eine beliebte Methode, um die Computerleistung zu messen. Die Zeitkomplexität der Berechnung aller Primzahlen unterhalb von n im Maschinenmodell mit wahlfreiem Zugriff beträgt O ( n log log n ) Operationen, eine direkte Folge der Tatsache, dass sich die harmonische Reihe der Primzahlen asymptotisch log log n nähert . Er hat jedoch eine exponentielle Zeitkomplexität in Bezug auf die Eingabegröße, was ihn zu einem pseudopolynomialen Algorithmus macht. Der Basisalgorithmus erfordert O ( n ) Speicher.

Die Bitkomplexität des Algorithmus beträgt O ( n ( log n ) ( log log n ) ) Bitoperationen mit einem Speicherbedarf von O ( n ) .

Die normalerweise implementierte seitensegmentierte Version hat die gleiche Betriebskomplexität von O ( n log log n ) wie die nicht-segmentierte Version, reduziert jedoch den Platzbedarf auf die sehr minimale Größe der Segmentseite plus den erforderlichen Speicher zum Speichern der Basisprimzahlen auf weniger als die Quadratwurzel des Bereichs, der verwendet wird, um Composites aus aufeinanderfolgenden Seitensegmenten der Größe O ( nein/Log- Nr) .

Eine spezielle (selten, wenn überhaupt, implementierte) segmentierte Version des Siebes von Eratosthenes mit grundlegenden Optimierungen verwendet O ( n ) Operationen und O (nlog log nr/Log- Nr) Speicherbits.

Die Verwendung einer großen O-Notation ignoriert konstante Faktoren und Offsets, die für praktische Bereiche sehr wichtig sein können: Das Sieb der Eratosthenes-Variation, das als Pritchard-Radsieb bekannt ist, hat eine Leistung von O ( n ) , aber seine grundlegende Implementierung erfordert entweder einen "One-Large-Array"-Algorithmus was seinen nutzbaren Bereich auf die Menge des verfügbaren Speichers beschränkt, andernfalls muss er seitensegmentiert werden, um den Speicherverbrauch zu reduzieren. Bei Implementierung mit Seitensegmentierung, um Speicher zu sparen, benötigt der Basisalgorithmus immer noch etwa O (n/Log- Nr) Speicherbits (viel mehr als die Anforderung des grundlegenden seitensegmentierten Siebs von Eratosthenes mit O (nein/Log- Nr) Speicherbits). Pritchards Arbeit reduzierte den Speicherbedarf auf Kosten eines großen konstanten Faktors. Obwohl das resultierende Radsieb eine O ( n )-Leistung und einen akzeptablen Speicherbedarf aufweist, ist es für praktische Siebbereiche nicht schneller als ein vernünftiges Radfaktorisiertes Basissieb von Eratosthenes.

Eulers Sieb

Eulers Beweis der Zeta-Produktformel enthält eine Version des Siebes von Eratosthenes, bei der jede zusammengesetzte Zahl genau einmal eliminiert wird. Das gleiche Sieb wurde von Gries & Misra (1978) wiederentdeckt und beobachtet, dass es lineare Zeit benötigt . Auch sie beginnt mit einer Liste von Zahlen von 2 bis n der Reihe nach. Bei jedem Schritt wird das erste Element als nächste Primzahl identifiziert, mit jedem Element der Liste multipliziert (also mit sich selbst beginnend) und die Ergebnisse in der Liste zum späteren Löschen markiert. Anschließend werden das Ausgangselement und die markierten Elemente aus dem Arbeitsablauf entfernt und der Vorgang wiederholt:

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

Hier wird das Beispiel ausgehend von den Quoten nach dem ersten Schritt des Algorithmus gezeigt. Somit werden im k- ten Schritt alle verbleibenden Vielfachen der k- ten Primzahl aus der Liste entfernt, die danach nur noch zu den ersten k Primzahlen koprime Zahlen enthält (vgl. Radfaktorisierung ), sodass die Liste mit der nächsten beginnt Primzahl, und alle Zahlen, die sich unterhalb des Quadrats ihres ersten Elements befinden, sind ebenfalls Primzahlen.

Somit sind beim Erzeugen einer begrenzten Folge von Primzahlen alle verbleibenden Zahlen in der Liste Primzahlen, wenn die nächste identifizierte Primzahl die Quadratwurzel der oberen Grenze überschreitet. Im obigen Beispiel wird dies erreicht, indem 11 als nächste Primzahl identifiziert wird, was eine Liste aller Primzahlen kleiner oder gleich 80 ergibt.

Beachten Sie, dass Zahlen, die von einem Schritt verworfen werden, weiterhin verwendet werden, während die Vielfachen in diesem Schritt markiert werden, z. B. für die Vielfachen von 3 ist es 3 × 3 = 9 , 3 × 5 = 15 , 3 × 7 = 21 , 3 × 9 = 27 , ..., 3 × 15 = 45 , ..., also ist hiermit Vorsicht geboten.

Siehe auch

Verweise

Externe Links