Sieve of Eratosthenes-Algorithmus: Python, C++-Beispiel (2024)

Das Sieb des Eratosthenes ist das einfachste Primzahlsieb. Es handelt sich um einen Primzahlalgorithmus zum Durchsuchen aller Primzahlen numbers in einer gegebenen Grenze. Es gibt mehrere Primzahlsiebe. Zum Beispiel das Sieb von Eratosthenes, Sieb von Atkin, Sieb von Sundaram usw.

Das Wort "Sieb„bezeichnet ein Gerät, das Substanzen filtert. Somit ist der Siebalgorithmus in Python und andere Sprachen bezieht sich auf einen Algorithmus zum Herausfiltern von Primzahlen numbers.

Dieser Algorithmus filtert die Primzahl in einem iterativen Ansatz heraus. Der Filtervorgang beginnt mit der kleinsten Primzahl. Eine Primzahl ist eine natürliche Zahl, die größer als 1 ist und nur zwei Teiler hat. viz., 1 und die Zahl selbst. Der numbers die keine Primzahlen sind, nennt man zusammengesetzt numbers.

Im Sieb der Eratosthenes-Methode wird zunächst eine kleine Primzahl ausgewählt und alle Vielfachen davon herausgefiltert. Der Prozess läuft in einer Schleife in einem bestimmten Bereich.

Beispielsweise:

Nehmen wir den Zahlenbereich von 2 bis 10.

Nach Anwendung des Siebes des Eratosthenes wird die Liste der Primzahlen erstellt numbers 2, 3, 5, 7

Algorithmus-Sieb von Eratosthenes

Hier ist der Algorithmus für das Sieb des Eratosthenes:

Schritt 1) Erstellen Sie eine Liste von numbers von 2 bis zum angegebenen Bereich n. Wir beginnen mit 2, da es die kleinste und erste Primzahl ist.

Schritt 2) Wählen Sie die kleinste Zahl in der Liste aus, x (anfänglich ist x gleich 2), durchlaufen Sie die Liste und filtern Sie die entsprechende Zusammensetzung numbers durch Markieren aller Vielfachen der ausgewählten numbers.

Schritt 3) Wählen Sie dann die nächste Primzahl oder die kleinste nicht markierte Zahl in der Liste und wiederholen Sie Schritt 2.

Schritt 4) Wiederholen Sie den vorherigen Schritt, bis der Wert von x kleiner oder gleich der Quadratwurzel von n sein sollte (x<=).

Hinweis: Die mathematische Begründung ist recht einfach. Der Zahlenbereich n kann faktorisiert werden als

n=a*b

Auch hier ist n =*

= (Faktor kleiner als ) * (Faktor größer als )

Also mindestens einer der Primfaktoren oder beide müssen <= sein. Also Überquerung zu wird genug sein.

Schritt 5) Nach diesen vier Schritten bleibt der Rest unmarkiert numbers wären alle Primzahlen in diesem gegebenen Bereich n.

Beispiel:

Nehmen wir ein Beispiel und sehen, wie es funktioniert.

Für dieses Beispiel finden wir die Liste der Primzahlen numbers von 2 bis 25. Also, n=25.

Schritt 1) Im ersten Schritt erstellen wir eine Liste numbers von 2 bis 25, da wir n=25 ausgewählt haben.

Schritt 2) Dann wählen wir die kleinste Zahl in der Liste aus, x. Anfangs ist x=2, da es sich um die kleinste Primzahl handelt. Dann durchlaufen wir die Liste und markieren die Vielfachen von 2.

Das Vielfache von 2 für den gegebenen Wert von n ist: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.

Hinweis: Die blaue Farbe kennzeichnet die ausgewählte Zahl und die rosa Farbe kennzeichnet die eliminierten Vielfachen

Schritt 3) Dann wählen wir die nächstkleinere nicht markierte Zahl, also 3, und wiederholen den letzten Schritt, indem wir die Vielfachen von 3 markieren.

Schritt 4) Wir wiederholen Schritt 3 auf die gleiche Weise, bis x= oder 5.

Schritt 5) Der Rest nicht markiert numbers wäre die Primzahl numbers von 2 zu 25.

Pseudocode

BeginDeclare a boolean array of size n and initialize it to trueFor all numbers i : from 2 to sqrt(n) IF bool value of i is true THEN i is prime For all multiples of i (i<n) mark multiples of i as compositePrint all unmarked numbersEnd

Sieb des Eratosthenes C/C++-Codebeispiel

#include <iostream>#include <cstring>using namespace std;void Sieve_Of_Eratosthenes(int n){ // Create and initialize a boolean array bool primeNumber[n + 1]; memset(primeNumber, true, sizeof(primeNumber)); for (int j = 2; j * j <= n; j++) { if (primeNumber[j] == true) { // Update all multiples of i as false for (int k = j * j; k <= n; k += j) primeNumber[k] = false; } } for (int i = 2; i <= n; i++) if (primeNumber[i]) cout << i << " ";}int main(){ int n = 25; Sieve_Of_Eratosthenes(n); return 0;} 

Ausgang:

2 3 5 7 11 13 17 19 23

Sieve of Eratosthenes Python-Programmbeispiel

def SieveOfEratosthenes(n):# Create a boolean arrayprimeNumber = [True for i in range(n+2)]i = 2while (i * i <= n):if (primeNumber[i] == True):# Update all multiples of i as falsefor j in range(i * i, n+1, i):primeNumber[j] = Falsei += 1for i in range(2, n):if primeNumber[i]:print(i)n = 25SieveOfEratosthenes(n)

Ausgang:

23571113171923

Segmentiertes Sieb

Wir haben gesehen, dass das Sieb des Eratosthenes benötigt wird, um eine Schleife durch den gesamten Zahlenbereich zu durchlaufen. Daher benötigt es O(n) Speicherplatz zum Speichern numbers. Kompliziert wird die Situation, wenn wir versuchen, Primzahlen in einem großen Bereich zu finden. Es ist nicht möglich, einen so großen Speicherplatz für ein größeres n zu reservieren.

Der Algorithmus kann durch die Einführung einiger neuer Funktionen optimiert werden. Die Idee besteht darin, den Zahlenbereich in kleinere Segmente zu unterteilen und Primzahlen zu berechnen numbers in diesen Segmenten nacheinander. Dies ist eine effiziente Möglichkeit, den Platzbedarf zu reduzierenplexität. Diese Methode heißt a segmentiertes Sieb.

Die Optimierung kann wie folgt erreicht werdenwing Weise:

1. Verwenden Sie ein einfaches Sieb, um Prime zu finden numbers von 2 zu und speichern Sie sie in einem Array.
2. Teilen Sie den Bereich [0…n-1] in höchstens mehrere Segmente der Größe auf
3. Iterieren Sie für jedes Segment das Segment und markieren Sie das Vielfache der Primzahl numbers finden Sie in Schritt 1. Dieser Schritt erfordert O() bei max.

Das reguläre Sieb benötigt O(n) zusätzlichen Speicherplatz, während das segmentierte Sieb O(), was eine große Verbesserung für ein großes n darstellt. Die Methode hat auch einen Nachteil, weil sie die Zeitkompensation nicht verbessertplexkeit.

Mitplexity-Analyse

Weltraumkomplexität:

Der einfache Sieb-of-Eratosthenes-Algorithmus benötigt O(n) Speicherplatz. Und das segmentierte Sieb erfordert
O() Hilfsraum.

Time Complexität:

Die Zeit complexDie Einheitlichkeit eines regulären Sieb-of-Eratosthenes-Algorithmus ist O(n*log(log(n))). Die Begründung hinter dieser Nachrichtplexität wird unten besprochen.

Für eine gegebene Zahl n die Zeit, die zum Markieren einer zusammengesetzten Zahl (d. h. Nicht-Primzahl) erforderlich ist numbers) ist konstant. Die Häufigkeit, mit der die Schleife ausgeführt wird, ist also gleich:

n/2 + n/3 + n/5 + n/7 + ……∞

= n * (1/2 + 1/3 + 1/5 + 1/7 +…….∞)

Der harmonische Verlauf der Summe der Primzahlen kann als log(log(n)) abgeleitet werden.

(1/2 + 1/3 + 1/5 + 1/7 +…….∞) = log(log(n))

Also, die Zeit kommtplexität wird-

T(n) = n * (1/2 + 1/3 + 1/5 + 1/7 + ……∞)

= n * log(log(n))

So ist die Zeit complexity O(n * log(log(n)))

Als nächstes erfahren Sie mehr darüber Pascals Dreieck

Zusammenfassung

• Das Sieb des Eratosthenes filtert die Primzahl heraus numbers in einer gegebenen Obergrenze.
• Das Filtern einer Primzahl beginnt mit der kleinsten Primzahl „2“. Dies geschieht iterativ.
• Die Iteration erfolgt bis zur Quadratwurzel von n, wobei n der angegebene Zahlenbereich ist.
• Nach diesen Iterationen ist die numbers die übrig bleiben, sind die Prime numbers.