Das Sieb des Eratosthenes in Python & C++

Was ist das Sieb des Eratosthenes?

Das Sieb des Eratosthenes ist das einfachste Primzahlsieb. Es ist ein Algorithmus, mit dem man alle Primzahlen innerhalb einer vorgegebenen Grenze finden kann. Es existieren mehrere Primzahlsiebe, darunter das Sieb des Eratosthenes, das Sieb von Atkin und das Sieb von Sundaram.

Das Wort "Sieb„“ bezeichnet ein Utensil, das Substanzen filtert. In diesem Sinne ist der Siebalgorithmus in Python und anderen Sprachen bezieht sich auf eine Methode, die Primzahlen aus einer Liste von ganzen Zahlen herausfiltert.

Dieser Algorithmus filtert Primzahlen iterativ. Der Filterprozess beginnt mit der kleinsten Primzahl. Eine Primzahl ist eine natürliche Zahl größer als 1, die nur zwei Teiler hat, nämlich 1 und sich selbst. Numbers Zahlen, die keine Primzahlen sind, werden zusammengesetzte Zahlen genannt.

Warum das Sieb des Eratosthenes verwenden?

Beim Sieb des Eratosthenes wird zunächst eine kleine Primzahl ausgewählt und anschließend alle Vielfachen davon herausgefiltert. Dieser Vorgang wird in einer Schleife über einen vorgegebenen Bereich wiederholt und liefert so effizient alle Primzahlen bis n, ohne für jede Zahl eine Probedivision durchzuführen.

Dadurch ist das Sieb schneller als die Primzahlprüfung für jede Zahl einzeln. Es findet breite Anwendung in der Zahlentheorie, Kryptographie, beim Hashing und im Wettbewerbsprogrammieren, wo viele Primzahlen schnell generiert werden müssen.

Beispielsweise:

Nehmen wir den Zahlenbereich von 2 bis 10.

Nach Anwendung des Siebs des Eratosthenes erhält man die Liste der Primzahlen 2, 3, 5, 7.

Algorithmus-Sieb von Eratosthenes

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

Schritt 1) Erstelle eine Liste von Zahlen von 2 bis zum angegebenen Bereich n. Wir beginnen mit 2, weil es die kleinste und erste Primzahl ist.

Schritt 2) Wähle die kleinste Zahl in der Liste, x (anfangs ist x gleich 2), durchlaufe die Liste und filtere die entsprechenden zusammengesetzten Zahlen, indem du alle Vielfachen der ausgewählten Zahl markierst.

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) Wiederhole den vorherigen Schritt, bis der Wert von x kleiner oder gleich der Quadratwurzel von n ist (x <= 0).).

Hinweis: Die mathematische Begründung ist recht einfach. Der Zahlenbereich n lässt sich wie folgt faktorisieren:

n = a * b

Auch hier ist n = *

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

Also mindestens einer der Primfaktoren oder beide müssen <= sein Daher durchquert man bis zu wird genug sein.

Schritt 5) Nach diesen vier Schritten sind die verbleibenden unmarkierten Zahlen alle Primzahlen in diesem gegebenen Bereich n.

Ausgearbeitetes Beispiel

Ejemplo:

Nehmen wir ein Beispiel und sehen wir uns an, wie es funktioniert.

In diesem Beispiel ermitteln wir die Liste der Primzahlen von 2 bis 25. Also ist n = 25.

Schritt 1) Im ersten Schritt nehmen wir eine Liste von Zahlen von 2 bis 25, da wir n = 25 gewählt haben.

Schritt 2) Dann wählen wir die kleinste Zahl der Liste, x. Zunächst ist x = 2, da dies die kleinste Primzahl ist. Anschließend durchlaufen wir die Liste und markieren alle Vielfachen von 2.

Die Vielfachen von 2 für den gegebenen Wert von n sind: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.

Hinweis: Die Farbe Blau kennzeichnet die ausgewählte Zahl, die Farbe Rosa die ausgeschlossenen 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 übrigen nicht markierten Zahlen sind die Primzahlen von 2 bis 25.

Pseudo-Code

Der folgende Pseudocode erfasst die Grundstruktur des Siebs des Eratosthenes, bevor wir ihn in tatsächlichen Code übersetzen.

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

Nachfolgend finden Sie eine vollständige C++ Implementierung des Siebs des Eratosthenes, das alle Primzahlen bis zu einer gewählten oberen Grenze ausgibt.

#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

Folgende Python Das Programm implementiert denselben Algorithmus mithilfe einer booleschen Liste und einer while-Schleife.

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 den gesamten Zahlenbereich durchläuft. Daher benötigt es O(n) Speicherplatz, um die Zahlen zu speichern. Die Situation wird kompliziert, wenn wir Primzahlen in einem sehr großen Bereich suchen, da es nicht praktikabel ist, für ein größeres n einen so großen Speicherblock zu reservieren.

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. Für jedes Segment wird das Segment durchlaufen und die Vielfachen der in Schritt 1 gefundenen Primzahlen markiert. Dieser Schritt benötigt O() maximal.

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

Komplexitätsanalyse

Das Verständnis sowohl der räumlichen als auch der zeitlichen Komplexität hilft Ihnen bei der Auswahl zwischen dem regulären Sieb und dem segmentierten Sieb für eine gegebene Problemgröße.

Raumkomplexität:

Der einfache Sieb-Algorithmus des Eratosthenes benötigt O(n) Speicherplatz. Der segmentierte Sieb-Algorithmus benötigt 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 im Folgenden erläutert.

Für eine gegebene Zahl n ist die Zeit, die zum Markieren einer zusammengesetzten Zahl (d. h. einer Nicht-Primzahl) benötigt wird, konstant. Daher entspricht die Anzahl der Schleifendurchläufe:

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

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

Die harmonische Folge der Summe der Primzahlen lässt sich wie folgt herleiten: log(log(n)):

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

Die Zeitkomplexität beträgt also:

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

= n * log(log(n))

Die Zeitkomplexität beträgt somit O(n * log(log(n))).

Als Nächstes erfahren Sie mehr über Pascals Dreieck.

Häufig gestellte Fragen