· 

Das Sieb des Eratosthenes

1. Einführung

Primzahlen (also Zahlen, die nur durch 1 und sich selbst teilbar sind), sind elementarer Bestandteil eines Großteils heutiger Verschlüsselungsverfahren. Ohne sie wäre ein Internet, in dem Personen sicher miteinander kommunizieren können und in dem Vertraulichkeit, Authentizität und Integrität sichergestellt sind, unmöglich. Das RSA-Verfahren berechnet bspw. mit zwei sehr großen Primzahlen einen öffentlichen und einen privaten Schlüssel, der eine asymmetrisch verschlüsselte Kommunikation ermöglicht.

Die Suche nach Primzahlen beschäftigt Mathematiker schon seit Jahrtausenden. Und trotzdem ist es bis heute Niemandem gelungen eine Formel zu finden, die zuverlässig (und in hinreichend kurzer Zeit) Primzahlen findet. Es gibt zahlreiche Primzahlentests, die probabilistischer Natur sind, d. h. es wird nur mit einer bestimmten Wahrscheinlichkeit (die aber sehr hoch ist) korrekt ermittelt, ob eine Zahl eine Primzahl ist oder nicht. Warum macht man das so? Weil naive Primzahlentests mit der Holzhammermethode in realen Anwendungen zu lange dauern.

2. Vorgehensweise

Das Sieb des Eratosthenes ist ein sehr einfacher (und intuitiver Weg), um Primzahlen zu finden.
Zunächst einmal legst du fest, in welchem Bereich du Primzahlen suchen willst. Wir gehen im Folgenden davon aus, dass du von \(2\) startest und bis \(100\) gehen willst. Warum starten wir bei \(2\) und nicht bei \(1\)? Nun, weil \(1\) per Definition keine Primzahl und \(2\) somit die erste Primzahl ist. Da du weißt, dass \(2\) eine Primzahl ist, kann \(4\) schon keine Primzahl mehr sein, da \(2\cdot 2=4\) ist. Auch \(6\) kann keine Primzahl mehr sein, weil \(2\cdot 3=6\) ist. Selbes gilt auch für \(8\), denn \(2\cdot 4 = 8\). Erkennst du langsam ein Muster? \(10\) fällt ebenfalls als Primzahlenkandidat raus, da \(2\cdot 5=10\) ist. Allgemein lässt sich sagen, dass alle ganzzahligen Vielfachen von \(2\) als Primzahlen ausscheiden, da \(2\cdot k\) wegen dem Faktor \(2\) keine Primzahl mehr sein kann.
Jetzt schaust du nach, welche Zahl nach der \(2\) noch nicht durchgestrichen wurde. Das ist in diesem Fall die \(3\). Also ist \(3\) eine Primzahl. Jetzt gehst du völlig analog zu dem Fall mit \(2\) vor und streichst nacheinander alle ganzzahligen Vielfachen der \(3\) bis hoch zur \(100\). Das wären \(6\) (die du zuvor schon gestrichen hast), \(9\), \(12\) (ebenfalls schon gestrichen), \(15\) usw..
Die nächste noch nicht durchgestrichene Zahl ist die \(5\), d. h. \(5\) ist eine Primzahl. Alle ganzzahligen Vielfachen der \(5\) bis hoch zur \(100\) fallen als Primzahlen raus.
\(7\) ist die nächste Zahl nach der \(5\), die noch nicht durchgestrichen wurde und deshalb handelt es sich hierbei um eine Primzahl. Auch hier werden wieder alle Vielfachen gestrichen.
Bei der nächsten Primzahl (nämlich \(11\)) wirst du feststellen, dass bis \(100\) kein ganzzahliges Vielfaches existiert, das du noch nicht zuvor gestrichen hast.
Eigentlich brauchst du bis \(100\) hier nicht mehr nach weiteren Zahlen suchen, die zu streichen sind. Warum? Nun, wenn du bis \(100\) suchst und du schon alle Teiler bis \(10\) geprüft hast, dann wird ein Teiler, der über \(10\) liegt einen Komplementärteiler (also ein Gegenstück, das man mit dem Teiler über \(10\) multipliziert) haben müssen, der kleiner als \(10\) ist, denn ansonsten kommt man über \(100\). Diese Eigenschaft kann man verallgemeinern und sagen, dass wenn du von \(2\) bis \(n\) suchst, du niemals weiter als bis \(\sqrt{n}\) suchen musst. Das kann man auch mathematisch beweisen. Für unseren Fall heißt das also, dass alle übriggebliebenen Zahlen, die ab der \(11\) folgen, keine weiteren Streichungen mehr vorgenommen genommen werden müssen, weil wir nur bis \(\sqrt{100}=10\) suchen müssen. Bei dem Rest in der Liste handelt es sich nur noch um Primzahlen. Wir haben also auf einen Schlag \(21\) weitere Primzahlen gefunden!

3. Implementierung in Python

Kommen wir nun zur Implementierung dieser Vorgehensweise in Python, um den Computer die lästige Arbeit für uns erledigen zu lassen.

Zuerst benötigen wir den Import math, um später die Wurzelfunktion verwenden zu können. Schließlich wollen wir uns die Eigenschaft, dass wir nur bis zur Wurzel aus n suchen müssen, zunutze machen.

import math

Als nächstes definieren wir uns eine Funktion, die wir eratosthenes nennen. Diese erhält als Übergabeparameter die Zahl n, bis zur der wir von der 2 beginnend Primzahlen suchen wollen.

def eratosthenes(n):

Als nächstes definieren wir uns eine zu Beginn leere Liste, in der wir die Primzahlen speichern, die wir nacheinander aufspüren.

primzahlen = []

Zudem erstellen wir eine Liste, die alle Zahlen von 2 bis n enthält. Das sind die Zahlen, die wir nacheinander streichen.

zahlen = list(range(2,n))

In der Variable aktuell speichern wir uns die aktuell betrachtete Zahl, für die wir dann die ganzzahligen Streichungen vornehmen werden. Zu Beginn liegt dieser Wert bei der ersten Primzahl, nämlich 2.

aktuell = 2

Solange der aktuelle Wert kleiner als die Wurzel aus n ist, führen wir Streichungen durch. Hier kommt uns also die Eigenschaft zugute, die uns den Suchbereich einschränkt.

while aktuell < math.sqrt(n):

Innerhalb dieser while-Schleife klappern wir nun in einer for-Schleife nacheinander alle Zahlen vom aktuellen Wert aktuell bis zum Endwert n ab und gehen dabei in aktuell vielen Schritten vor. Dadurch bekommen wir in Python die ganzzahligen Vielfachen von aktuell.

for _ in range(aktuell, n, aktuell):
Wenn wir die Zahl _ in diesem Zahlenbereich finden sollten und damit ein ganzzahliges Vielfaches von aktuell finden, dann entfernen wir dieses Element aus der Liste.
if _ in zahlen:
   zahlen.remove(_)
Wenn wir am Ende der for-Schleife angekommen sind fügen wir die Zahl aktuell der Primzahlenliste hinzu. Klar, von dieser Zahl aus haben wir ja unsere Vielfachen gesucht und gestrichen.
primzahlen.append(aktuell)

Jetzt müssen wir für den nächsten Durchlauf der while-Schleife noch einen neuen Wert für aktuell festlegen. Das ist ganz einfach das Element, das ganz vorne in der Liste unseres Suchbereichs steht. Wir suchen ja immer die erste nicht durchgestrichene (bzw. in unserer Implementierung aus der Liste entfernte) Zahl nach der Zahl, die wir als Primzahl identifiziert haben.

aktuell = zahlen[0]

Damit wir am Ende sowohl unsere Primzahlen, als auch die nicht durchgestrichenen Elemente über der Wurzel aus n als Ergebnis zurückliefern können, fügen wir die beiden Teillisten mit einem Plus zusammen.

return primzahlen + zahlen
Ein Aufruf dieser Funktion mit n=10 würde z. B. nur bis \(\sqrt{1000}\) (also ungefähr \(31\)) suchen.

4. Quellcode

import math

def eratosthenes(n):
    primzahlen = []
    zahlen = list(range(2,n))
    aktuell = 2
    while aktuell < math.sqrt(n):
        for _ in range(aktuell, n, aktuell):
            if _ in zahlen:
                zahlen.remove(_)
        primzahlen.append(aktuell)
        aktuell = zahlen[0]
    return primzahlen + zahlen
    
print(eratosthenes(100))