Sieb des Eratosthenes-Algorithmus: Python, C++ Beispiel

Das Sieb des Eratosthenes ist das einfachste Primzahlsieb. Es ist ein Primzahlalgorithmus, um alle Primzahlen in einem bestimmten Bereich zu suchen. Es gibt mehrere Primzahlsiebe. Zum Beispiel das Sieb des Eratosthenes, das Sieb von Atkin, das Sieb von Sundaram usw.

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

Dieser Algorithmus filtert die Primzahlen iterativ 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, nämlich 1 und die Zahl selbst. Die Zahlen, die keine Primzahlen sind, heißen zusammengesetzte Zahlen.

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 2, 3, 5, 7 erstellt

Algorithmus-Sieb von Eratosthenes

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

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

Schritt 2) Wählen Sie die kleinste Zahl auf der Liste, x (anfangs ist x gleich 2), durchlaufen Sie die Liste und filtern Sie die entsprechenden zusammengesetzten Zahlen, indem Sie alle Vielfachen der ausgewählten Zahlen markieren.

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 wären die verbleibenden nicht markierten Zahlen alle Primzahlen in dem gegebenen Bereich n.

Ejemplo:

Nehmen wir ein Beispiel und sehen, wie es funktioniert.

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

Schritt 1) Im ersten Schritt nehmen wir eine Liste mit Zahlen 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) Die restlichen nicht markierten Zahlen wären die Primzahlen von 2 bis 25.

Pseudocode

Begin
	Declare a boolean array of size n and initialize it to true
	For 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 composite
Print all unmarked numbers
End

Sieb des Eratosthenes C/C++ Code Beispiel

#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

Sieb von Eratosthenes Python Programmbeispiel

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

Ausgang:

2
3
5
7
11
13
17
19
23

Segmentiertes Sieb

Wir haben gesehen, dass das Sieb des Eratosthenes eine Schleife durch den gesamten Zahlenbereich ausführen muss. Es benötigt also O(n) Speicherplatz, um die Zahlen zu speichern. Die Situation wird komplizierter, wenn wir versuchen, Primzahlen in einem riesigen Bereich zu finden. Es ist nicht möglich, einen so großen Speicherplatz für ein größeres n zuzuweisen.

Der Algorithmus kann durch die Einführung einiger neuer Funktionen optimiert werden. Die Idee besteht darin, den Zahlenbereich in kleinere Segmente aufzuteilen und die Primzahlen in diesen Segmenten einzeln zu berechnen. Dies ist eine effiziente Möglichkeit, die Speicherkomplexität zu reduzieren. Diese Methode wird als segmentiertes Sieb.

Die Optimierung kann auf folgende Weise erreicht werden:

1. Verwenden Sie ein einfaches Sieb, um Primzahlen von 2 bis zu finden 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 durch das Segment und markieren Sie das Vielfache der in Schritt 1 gefundenen Primzahlen. Dieser Schritt erfordert O() bei max.

Das reguläre Sieb benötigt O(n) zusätzlichen Speicherplatz, während das segmentierte Sieb O(), was bei einem großen n eine große Verbesserung darstellt. Die Methode hat aber auch einen Nachteil, da sie die Zeitkomplexität nicht verbessert.

Komplexitätsanalyse

Raumkomplexität:

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

Zeitliche Komplexität:

Die Zeitkomplexität eines regulären Sieb-des-Eratosthenes-Algorithmus beträgt O(n*log(log(n))). Die Gründe für diese Komplexität werden weiter unten erläutert.

Für eine gegebene Zahl n ist die Zeit, die zum Markieren einer zusammengesetzten Zahl (also einer Nichtprimzahl) benötigt wird, konstant. Die Anzahl der Schleifendurchläufe 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))

Die zeitliche Komplexität wird also sein:

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

= n * log(log(n))

Somit ist die Zeitkomplexität O(n * log(log(n)))

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

Zusammenfassung

• Das Sieb des Eratosthenes filtert die Primzahlen innerhalb einer vorgegebenen Obergrenze heraus.
• 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 sind die verbleibenden Zahlen die Primzahlen.