Sieve of Eratosthenes-Algorithmus: Python, C++-Beispiel

Das Sieb des Eratosthenes ist das einfachste Primzahlsieb. Es handelt sich um einen Primzahlalgorithmus zum Durchsuchen aller Primzahlen in einem bestimmten Grenzwert. 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.

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. Die Zahlen, die keine Primzahlen sind, werden zusammengesetzte Zahlen genannt.

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.

Sieb des Eratosthenes-Algorithmus

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

Sieb des Eratosthenes-Algorithmus

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 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 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<=Algorithmus-Sieb von Eratosthenes).

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

n=a*b

Auch hier ist n =Algorithmus-Sieb von Eratosthenes*Algorithmus-Sieb von Eratosthenes

= (Faktor kleiner als Algorithmus-Sieb von Eratosthenes) * (Faktor größer als Sieb des Eratosthenes-Algorithmus)

Also mindestens einer der Primfaktoren oder beide müssen <= seinAlgorithmus-Sieb von Eratosthenes. Also Überquerung zu Algorithmus-Sieb von Eratosthenes wird genug sein.

Schritt 5) Nach diesen vier Schritten wären die verbleibenden unmarkierten Zahlen 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 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.

Algorithmus-Sieb von Eratosthenes

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.

Sieb des Eratosthenes-Algorithmus

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.

Sieb des Eratosthenes-Algorithmus

Schritt 4) Wir wiederholen Schritt 3 auf die gleiche Weise, bis x=Sieb des Eratosthenes-Algorithmus oder 5.

Sieb des Eratosthenes-Algorithmus

Schritt 5) Die verbleibenden nicht markierten Zahlen wären die Primzahlen von 2 bis 25.

Sieb des Eratosthenes-Algorithmus

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++-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 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 benötigt wird, um eine Schleife durch den gesamten Zahlenbereich zu durchlaufen. Daher benötigt es O(n) Speicherplatz zum Speichern der Zahlen. 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 in diesen Segmenten nacheinander Primzahlen zu berechnen. 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 Primzahlen von 2 bis zu finden Segmentiertes Sieb und speichern Sie sie in einem Array.
  2. Teilen Sie den Bereich [0…n-1] in höchstens mehrere Segmente der Größe auf Segmentiertes Sieb
  3. Iterieren Sie für jedes Segment das Segment und markieren Sie das Vielfache der in Schritt 1 gefundenen Primzahlen. Dieser Schritt erfordert O(Segmentiertes Sieb) bei max.

Das reguläre Sieb benötigt O(n) zusätzlichen Speicherplatz, während das segmentierte Sieb O(Segmentiertes Sieb), 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(Mitplexity-Analyse) 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 ist die Zeit, die zum Markieren einer zusammengesetzten Zahl (dh Nicht-Primzahl-Zahlen) erforderlich 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 Primzahlen in einer gegebenen 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.