Der Sieb des Eratosthenes

Einführung

In meinem letzten Blogbeitrag habe ich den Euklidischen Algorithmus beschrieben. Diesmal geht es um einen weiteren antiken Algorithmus. Es handelt sich um den Algorithmus  „Sieb des Eratosthenes“ und dieser ist der Erste uns bekannte Algorithmus zur Bestimmung aller Primzahlen, welche kleiner oder gleich einer vorgegebenen Zahl ist.

Was sind Primzahlen? Primzahlen sind natürliche Zahlen welche nur durch 1 und durch sich selbst teilbar sind. Doch bevor ich auf die Beschreibung des Verfahrens und auf Primzahlen eingehe, möchte ich noch Einiges zur dessen historischer Entwicklung erzählen. 

Historische Entwicklung

Die Griechen waren die Ersten die sich mit Primzahlen beschäftigt haben. Vor allem die Mathematiker der pytagoreischen Schule (500-300 v. Chr.) beschäftigten sich intensiv mit diesen. Die Pytagoräer „spielten“ und „experementierten“ eher mit diesen Zahlen. Erst Euklid in seinem epischem Werk „Elemente“ (300 v. Chr.) hievte die Primzahlen auf ein „saubares“ mathematisches Fundament. Euklid bewies in seinem Werk zwei der wichtigsten Grundlagen der Arithmetik. Die erste, dass es unendliche viele Primzahlen gibt und die zweite, dass jede ganze Zahl eindeutig als das Produkt von Primzahlen geschrieben werden kann. Die Primzahlen sind also so etwas wie die „Erzeuger“ aller ganzen Zahlen. Übrigens, die Zahl „1“ ist keine Primzahl! Warum, können sie hier erfahren. Doch kommen wir jetzt erst zum „Sieb des Eratosthenes“.

Eratosthenes von Kyrene lebte im 3. Jh. v. Chr. und wie auch Euklid den Euklidischen Algorithmus nicht entdeckte, entdeckte Eratosthenes auch nicht den „Sieb des Eratosthenes“, sondern formalisierte diesen und gab ihm dann die Bezeichnung „Sieb“. Das Verfahren war schon seit langer Zeit bekannt. Eratosthenes war ein außergewöhnlich vielseitiger griechischer Gelehrter. Er war als Mathematiker, Geograph, Astronom, Historiker, Philologe, Philosoph und Dichter tätig. Ein halbes Jahrhundert leitete er die Bibliothek von Alexandria. Zu erwähnen ist auch, dass Eratosthenes beruhend auf seinen sehr sorgfältigen Messungen, den Erdumfang bestimmen konnte. Die Zeit der großen griechischen Mathematiker endete mit Eratosthenes.

Beschreibung

Ich möchte das Prinzip hinter diesem Algorithmus anhand eines einfachen Beispiels zeigen und später auf die Verallgemeinerung und Implementierung (natürlich wieder in Python) eingehen. Wie gehabt, kann man sich den Beweis hier ansehen.

Nun zum Beispiel:

Liste von Zahlen von 2 bis 50

Betrachten wir eine Liste von Zahlen {2,…,50}. Nun möchten wir alle Primzahlen finden, die innerhalb dieser Liste liegen.

Wir fangen mit der 2 an und streichen alle Vielfachen aus der Liste

 Die erste Primzahl ist die 2. Jetzt streichen wir alle Vielfachen der 2 aus dieser Liste heraus (das können keine Primzahlen sein).

Danach die nächste freie Zahl, welche die 3 ist.

Jetzt kommt die nächste Zahl an die Reihe. Dies ist die 3 und sie ist eine Primzahl. Auch jetzt streichen wir alle Vielfachen der 3 aus unserer Liste.

… dann die 5

Die nächste freie Zahl ist die 5. Auch hier streichen wir die Vielfachen der 5 die noch nicht durchgestrichen worden sind.

am Ende kommt die 7 (da 7*7=49<50)

Jetzt kommt die 7 und es wird die 49 durchgestrichen.

Jetzt sind wir fertig und was noch übrig geblieben ist, müssen Primzahlen sein.

Und jetzt? Jetzt sind wir fertig! Warum? Die nächste Zahl wäre die 11. Aber mit welcher Zahl auch immer ich die 11 multipliziere, sie musste kleiner als 11 gewesen sein, da das Produkt nicht größer sein darf als 50. Diese Multiplikationen haben wir jedoch bereits schon hinter uns gebracht. Das bedeutet, dass es reicht, wenn wir immer die Zahlen in der Liste überprüfen bis zur ganzzahligen Wurzel von 50. Dies wäre in unserem Fall die 7 (7*7=49<50<11*11=121).

Wir sehen anhand des Beispiels, dass die Idee hinter dem Algorithmus ist, sukzessive alle Zahlen die keine Primzahlen sind aus der Liste rauszuschmeissen. Die Primzahlen bleiben wie in einem Sieb hängen und deshalb heißt das Verfahren auch „der Sieb des Eratosthenes“.

Das Verfahren

Der Algorithmus zur Bestimmung aller Primzahlen aus einer Liste geht wie folg:

  1. Es wird die kleinste Zahl aus der Liste ausgewählt und umkreist. Danach werden alle vielfachen dieser Zahl aus der Liste gestrichen.
  2. Danach wird die nächste nicht durchgestrichene Zahl aus der Liste umkreist und alle weiteren Vielfachen aus der Liste gestrichen.
  3. Das Verfahren (2) wiederholt sich, bis keine weiteren Zahlen zum streichen übrig bleiben.
  4. Das Verfahren endet und alle umkreisten Zahlen müssen Primzahlen sein. 

Das Nassi-Shneiderman-Diagramm sieht wie folgt aus:

Die Python Implementierung

Es gibt sehr viele Implementierungen des Algorithmus. Ich möchte zwei von ihnen hervorheben. Die erste Implementierung [1] ist einfach zu lesen und bildet den Algorithmus „straightforward“ ab. Sie hat daher einen starken didaktischen Charakter.

def sieb(n):
    P = range(2,n+1)            
    i = 0                      
    p = P[i]                  
    while p*p <= n:             
        v = 2*p                 
        while v <= P[-1]:      
            if v in P:         
                P.remove(v)     
            v = v+p             
        i = i+1
        p = P[i]
    return P

Die zweite Implementierung [2] des Algorithmus ist wesentlich anspruchsvoller aber dafür stark optimiert. Es bedarf einiger Zeit, um den Algorithmus zu erkennen. Am besten versteht man den Code, wenn man ihn in einem jupyter notebook schrittweise ausführt. Der Vorteil, diesen Aufwand zu betreiben ist, dass man zusätzlich zum optimierten Code auch etwas über effiziente Python Programmierung lernt.

def sieve(n):
    b, p, ps = [True] * (n+1), 2, []
    for p in xrange(2, n+1):
        if b[p]:
            ps.append(p)
            for i in xrange(p, n+1, p):
                b[i] = False
    return ps

Zusammenfassung

Primzahlen sind etwas sehr Fundamentales in der Mathematik. Sie scheinen so etwas wie die „Erzeuger“ von Zahlen zu sein. Sie sind aber auch etwas sehr „Teueres“. Teuer, weil es sehr viel Aufwand kostet, diese zu ermitteln oder aus anderen Zahlen „rauszufiltern“. Das ist auch der Grund warum Primzahlen einen fundamentale Rolle in der Kryptographie spielen. Konkret zu nennen ist hier die RSA-Verschlüsselung. Diese ist heute nicht mehr aus dem Internet und dem Zahlungsverkehr (Homebanking) wegzudenken. Doch bevor ich auf diesen Verschlüsselungsalgorithmus eingehe, muss ich noch etwas über die Modulare Arithmetik sagen. Ich nenne diese Arithmetik auch „Rechnen mit Uhren“ und sie ist das Thema meines nächsten Blogs.   

Anhang

Zu guter letzt: Warum ist die 1 keine Primzahl? Die Mathematiker haben sich erst im 20. Jahrhundert darauf geeinigt, dass die 1 keine Primzahl ist. Meiner Meinung nach sind die wichtigsten Gründe die, dass 

  • … jede Primzahl immer zwei Teiler haben muss. Die 1 und sich selber. Das ist bei der 1 nicht der Fall.
  • … wenn zwei Primzahlen miteinander multipliziert werden, dann auch eine andere Zahlen rauskommen muss. Wir haben ja auch ganz zu Anfang gesagt, dass die Primzahlen so etwas wie die „Erzeuger“ von Zahlen sind. Das funktioniert nicht, wenn man eine andere Primzahl mit der 1 multipliziert. 

Referenzen

  1. https://www.hsg-kl.de/facher/inf/python/listen/index.php
  2.  https://programmingpraxis.com/programming-with-prime-numbers-source-code-in-python/

Add a Comment

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.