Qbi's Weblog

Von Primzahlen geht für viele eine große Faszination aus das Thema wird aus verschiedenen Richtungen gern beleuchtet. Sehr alt ist dabei die Fragestellung, wie viele Primzahlen es denn gibt. Euklid fand neben anderen die Antwort auf diese Frage: Es gibt unendlich viele Primzahlen. Sein Beweis ist recht einleuchtend.

Stellen wir uns vor, es gäbe nur endlich fünf Primzahlen (In der Regel sagt man: endlich viele) p1, p2, p3, p4 und p5. Dann berechnet man eine neue Zahl z = p1*p2*p3*p4*p5+1, d.h. alle Primzahlen werden multipliziert und anschließend wird die Zahl 1 addiert. Keine der bisherigen Primzahlen teilt diese Zahl z. Da aber jede natürliche Zahl einen Primteiler besitzt, muss der außerhalb der bisher bekannten Primzahlen liegen, d.h. es gibt mindestens eine neue Primzahl p6. Die Aussage lässt sich dann wieder anwenden und so ergibt sich, dass die Zahl der Primzahlen nicht endlich sein kann.

Bei Mathoverflow wurden diverse Fehleinschätzungen diskutiert. Unter anderem zählte dazu, dass die oben konstruierte Zahl z eine Primzahl sei. Wenn man den Beweis oberflächlich liest (siehe auch die Skripte zu Algebra 1 oder Zahlentheorie), könnte man in der Tat zu dem Schluss kommen. Die Zahlen 2, 3, 5, 7, 11 und 13 liefern jedoch ein Gegenbeispiel.

Schlimm finde ich dann die in dem Posting angegebenen Beispiele von Leerern (sic!), die ihre Schülern unter Beschimpfungen vor die Tür stellen, weil sie auf den obigen Umstand hinweisen und den auch noch beweisen.

Bislang konnte ich die Eulerschen Probleme mit einem naiven Programmieransatz lösen. Das heißt, die erste Idee, die mir in den Kopf kam, schrieb ich runter und bekam eine Lösung. Das zehnte Problem warf mir einen Stock zwischen die Beine. Erstmals musste ich mir Gedanken über die Optimierung des Codes machen.

Das zehnte Problem klingt erstmal ganz harmlos: Finden Sie die Summen aller Primzahlen, die kleiner als 2 000 000 sind.. Ha, das ist ja eine einfache Fingerübung:

sieb = [ i for i in xrange(2,2000000) ]
for i in xrange(2,2000000):
  for j in xrange(2,2000000):
    if i*j in sieb:
      sieb.remove(i*j)

Die Werte in sieb müssen dann nur noch addiert werden und fertig. Jedoch kam ich gar nicht soweit. Denn das Programm lief und lief und lief.

Das brachte mich zum Nachdenken, woran das liegen könnte. Letztlich ist die Ursache offensichtlich. Denn der Code berechnet jedes Produkt. Dafür werden schon 2 000 000 * 2 000 000 = 4 000 000 000 000 Berechnungen durchgeführt. Wenn man von der (viel zu optimistischen) Variante ausgeht, dass jede Berechnung ein CPU-Zyklus ist, würde das Programm auf aktuellen Architekturen länger als eine halbe Stunde laufen. In der Realität lief es 15 Stunden. Wie lässt sich die Laufzeit nun verbessern?

Es ist recht offensichtlich, dass das Programm zuviel berechnet. Im ersten Schleifendurchlauf gibt es die Multiplikationen: 2*2, 2*3, 2*4, ..., 2*1999999 = 3999998. Beim zweiten Schleifendurchlauf: 3*2, 3*3, 3*4, ..., 3*1999999 = 5999997. Am klarsten fällt es im letzten Durchlauf auf: 1999999*2, 1999999*3, ..., 1999999*1999999 = 3999996000001. Die Berechnung 3*2 wurde schon im ersten Schritt (nur umgekehrt mit 2*3) durchgeführt. Hier wirkt das Kommutativgesetz. Also kann die Schleife im zweiten Durchlauf erst bei drei beginnen. Im dritten Durchlauf würde nach obigem Algorithmus 4*2, 4*3, 4*4 usw. berechnet werden. Verallgemeinert lässt sich also sagen, dass die Variable der zweiten Schleife genausogroß oder größer als die erste Variable sein muss. Dieser Schritt halbiert die Zahl der Berechnungen.

In der obigen Darstellung wird klar ersichtlich, dass das Programm nicht in jedem Fall bis zum Maximum von 2 000 000 laufen muss. Schon im ersten Durchlauf werden Werte über 2 000 000 berechnet. Das heißt, das Produkt i*j muss kleiner oder gleich 2 000 000 sein. Umformen nach j ergibt: j?2 000 000/i. Eine weitere oft genutzte Optimierung ist es, die erste Schleifenvariable nur bis ?2000000 laufen zu lassen.

Weiterhin fiel mir auch ein, dass man schon die initiale Liste nicht mit Zahlen von 2 bis 2 000 000 füllen muss. Denn es ist bekannt, dass alle Vielfachen von 2 sofort ausfallen. Man kann sogar soweit gehen, dass man nur Zahlen nach dem Muster 6*n-1 und 6*n+1 aufnimmt. Denn die Zahlen 6*n+0, 6*n+2 und 6*n+4 sind gerade und damit keine Primzahlen. Die Zahl 6*n+3 entspricht 3(2*n+1) und ist somit durch drei teilbar. Es verbleibt das obige Muster.

Theoretisch hätetn die obigen Anpassungen schon reichen sollen, um die Laufzeit unter eine Minute zu drücken. Jedoch lief das Programm immer nach weitaus länger. Nach einigem Stöbern fiel mir dann auf, dass in Python die Listenoperationen in und remove die Listen von Beginn an durchsuchen. Das bringt natürlich nochmal eine extreme Pessimierung der Laufzeit. Stattdessen sollte man hier Sets oder Dictionaries nutzen. Ich habe es mit Sets probiert und prompt lief das Programm schnell genug.

sieb = {}
for i in xrange(2, 2000000):
  sieb[i] = True
for x in xrange(2,int(math.sqrt(2000000))+1):
  if sieb[x] == True:
    for y in xrange(2000000/x, x-1,-1):
      t = x * y
      sieb[t] = False

Grundsätzlich lassen sich weitere Möglichkeiten der Optimierung ausdenken. Jedoch reichte mir das obige Ergebnis, um das Ziel zu erreichen. Wahrscheinlich benötige ich in späteren Aufgabe noch eine weitere Verbesserung.

Momentan bin ich etwas in Leselaune und verbringe noch dazu einige Zeit im Zug. Also versuche ich einige der im Schrank stehenden, ungelesenen Bücher anzuschauen oder komplett zu lesen. Vor kurzem fiel meine Wahl auf das Buch “Die Musik der Primzahlen. Auf den Spuren des größten Rätsels der Mathematik” von Marcus de Sautoy.

Wie der Name des Buches schon sagt, geht es im weiteren Sinne um Primzahlen. Der Autor geht zum Großteil auf die Untersuchung der Riemannschen Hypothese ein und erklärt, wer bisher daran gescheitert ist. Es ist ein interessanter historischer Abriss. Der Leser lernt eine Vielzahl groß(artig)er Mathematiker kennen. Falls jemand Angst hat, zuviel Mathematik zu finden, den kann ich beruhigen. Der Autor scheut aus meiner Sicht die Erwähnung mathematischer Details wie der Teufel das Weihwasser. Selbst recht einfache Sachverhalte wie die Modulorechnung werden anhand umständlicher Beispiele erklärt. Das ist gleichwohl einer der Punkten, die mir bei dem Buch nicht gefallen haben. Denn aus meiner Sicht kann man dem Leser schon mathematische Grundlagen zumuten.

Die erste Hälfte des Buches deckt die Geschichte bis etwa zu Beginn des 20. Jahrhunderts ab. Dies lässt sich angenehm und flüssig lesen. Zu Beginn der zweiten Hälfte des Buches fragte ich mich schon, was der Autor denn noch schreiben will. Tatsächlich wird dann hier vieles in die Länge gezogen bzw. es werden noch unnötige Details erklärt. Hier hätte ich es besser gefunden, wenn der Autor den Schreibstil der ersten Hälfte beibehalten hätte. Das Resultat wäre ein Buch mit vielleicht 50--100 Seiten weniger. Aber dann wäre der Gesamteindruck auf mich noch besser gewesen.

Letztlich sind die obigen Kritikpunkte jedoch Feinheiten. Insgesamt hat mir das Buch sehr gut gefallen, wenngleich ich etwas mehr Mathematik erwartet hätte. Solltet Ihr an der Geschichte dieser Wissenschaft interessiert sein, dann schaut es euch unbedingt mal an.