Ein Algorithmus zur Berechnung von Primzahlen

Das bekannteste Verfahren zur systematischen Berechnung aller Primzahlen in einem Intervall von 2 bis zu einer Schranke n ist wohl das Sieb des Eratosthenes. Es beruht darauf, daß man aus einer Liste aller Zahlen von 2 bis n, bei der kleinsten Primzahl beginnend, die Vielfachen der Primzahlen streicht, bis nur noch Primzahlen in der Liste stehen. Wenn man hierbei die größte Primzahl abgearbeitet hat, die kleiner als die Quadratwurzel von n ist, ist man auch schon fertig.

Eine weitere Methode zur Berechnung der Primzahlen in einem Intervall von 2 bis n, sieht so aus, daß man alle Zahlen des Intervalles (bei 3 beginnend aufsteigend) systhematisch darauf testet, ob sie durch eine kleinere Primzahl teilbar sind. Wenn das für eine getestete Zahl nicht zutrifft, ist sie eine Primzahl. Zur Feststellung der Teilbarkeit oder Nichtteilbarkeit bedient man sich in der Regel der Modulofunktion. Diese liefert den Rest aus der Division zweier Zahlen. Dieses Verfahren werde ich zur Unterscheidung von den anderen Verfahren im folgenden Moduloverfahren nennen.

Das Sieb des Eratosthenes ist das schnellere der beiden Verfahren. Das liegt vor allem daran, daß die Modulooperation zwar nicht so aufwendig ist, wie eine Division, aber immer noch vergleichsweise komplex. Dafür ist - bei der Ausführung auf einem Computer - der Speicherbedarf für das Sieb des Eratosthenes höher, denn man geht ja von einer Liste aller Zahlen des zu untersuchenden Intervalls aus, für die dann auch Speicherplätze zur Verfügung gestellt werden müssen.

Im Fortlauf wird ein Algorithmus entwickelt, der vom prinzipiellen Vorgehen dem Moduloverfahren ähnlich ist, aber dennoch wesentliche Strukturmerkmale des Verfahrens "Sieb des Eratosthenes" zeigt.

Wie schon erwähnt, besteht der Hauptgrund für die geringere Geschwindigkeit des Moduloverfahrens in der Komplexität der Modulofunktion. Von daher stellt sich die Frage, wie die Teilbarkeit einer Zahl durch eine Primzahl auf andere Art und Weise festgestellt werden kann.

Eine triviale Möglichkeit bestünde darin, statt der Anwendung der Modulooperation (die uns eine Programmiersprache anbietet), sooft durch wiederholte Aufsummierung das Vielfache einer Primzahl zu bilden, bis das Ergebnis größer oder gleich der zu testenden Zahl ist. Ist die Summe gleich der Zahl, so ist sie keine Primzahl.

Statt z modulo p führen wir also aus:

summe = p;
while (summe <= z)
{
summe = summe + p;
}
if summe > z then prim(p);

Wir könnten nun einfach jede Modulooperation durch die beschriebene Aufsummierung ersetzen. Allerdings wären wir dadurch noch nicht weitergekommen, da diese Summenbildung sicher mindestens so aufwendig ist, wie die Durchführung der Modulooperation.

Es ist aber nicht nötig, beim Test jeder neuen Zahl der Zahlengeraden, die Summenbildung bis zu dieser Zahl für jede Primzahl von Anfang an neu durchzuführen. Wir können einfach so vorgehen, daß wir uns, wenn wir das erstenmal das Vielfache einer Primzahl (durch Aufsummierung) gebildet haben, dieses Ergebnis merken. Wenn wir dann die nächste Zahl auf Teilbarkeit mit dieser Primzahl testen, setzen wir einfach bei der schon gebildeten Summe auf und addieren die Primzahl zu dieser Summe hinzu.

Es ergibt sich der folgende Ablauf:

Die erste Primzahl ist bekanntermaßen 2.

Wir beginnen mit der nächsthöheren Zahl, der 3.

Die erste Primzahl addieren wir mit sich selbst: 2 + 2 = 4. Da 4 größer als 3 ist und sich 3 nicht als Vielfaches einer kleineren Primzahl darstellen läßt, ist 3 eine Primzahl. Die Summe 4 merken wir uns zur ersten Primzahl.

Weiter auf der Zahlengeraden geht es mit der 4. Die gemerkte Summe zur ersten Primzahl ist 4. Das heißt die 4 läßt sich aus dem Vielfachen der ersten Primzahl (der 2) darstellen und ist keine Primzahl.

Jetzt geht es mit der 5 weiter. Die zur ersten Primzahl gemerkte Summe (4) ist kleiner als 5. Wir addieren wieder die erste Primzahl hinzu und erhalten 6. 6 ist größer als 5. Die Summe 6 merken wir uns wieder zur ersten Primzahl. Zur zweiten Primzahl (3) addieren wir diese hinzu und erhalten ebenfalls 6, was wir uns zur zweiten Primzahl merken. 5 läßt sich also weder als Summe der ersten noch der zweiten Primzahl darstellen und ist eine Primzahl.

Weiter mit der 6. Die zur ersten Primzahl gemerkte Summe ist gleich der 6. Also ist 6 keine Primzahl.

Weiter mit der 7:
6 < 7; 6 + 2 = 8; 8 > 7; (die Summe 8 wird zur 1. Primzahl gemerkt)
6 < 7; 6 + 3 = 9; 9 > 7; (die Summe 9 wird zur 2. Primzahl gemerkt)
5 < 7; 5 + 5 = 10 > 7; (die Summe 10 wird zur 3. Primzahl gemerkt)
Also ist 7 eine Primzahl.

usw.

Auch werden, wenn die Primzahlen von 1 bis n berechnet werden sollen, - ähnlich wie beim Sieb des Eratosthenes - nur die Summen der Primzahlen von 2 bis zur Quadratwurzel von n benötigt.

Das Vorliegen des Algorithmus wurde am 5. 6. 2000 notariell festgestellt.

Verglichen mit dem Moduluverfahren ist das Summenverfahren wesentlich schneller, was sich erst recht bemerkbar macht, wenn es nicht über eine interpretierte Skriptsprache, sondern über kompilierten Code ausgeführt wird.

Mit dem Sieb des Eratosthenes verbindet das Summenverfahren einige interessante Parallelen, obwohl das grundsätzliche Vorgehen ganz verschieden ist, denn während beim Sieb des Eratosthenes Vielfache von Primzahlen aus einer zuvor erstellten Liste natürlicher Zahlen gestrichen werden, bis die Liste nur noch Primzahlen enthält, werden beim Summenverfahren die Primzahlen eines Intervalles beginnend bei der 3 und aufsteigend bis zur größten Primzahl berechnet und können eine neue Liste bilden.

Nehmen wir an, die Primzahlenvielfachen, die beim Sieb des Eratosthenes benötigt werden, werden durch fortgesetzte Addition erzeugt, was ökonomisch und sinnvoll ist, so sind die arithmetischen Operationen, die beim Summenverfahren und beim Sieb des Eratosthenes zur Berechnung der Primzahlen eines Intervalles benötigt werden, identisch, d. h. im Endeffekt werden die gleichen Zahlen zu den gleichen Summen addiert.

Das Summenverfahren benötigt aber wesentlich weniger Speicherplatz. Beim Sieb des Eratosthenes entspricht der Speicherplatz zur Berechnung der Primzahlen eines Intervalles von 2 bis n der Anzahl der natürlichen Zahlen im Intervall (also n - 1) sowie einer vom Intervall unabhängigen konstanten Anzahl von "Hilfsspeicherplätzen". Beim Summenverfahren beträgt die Anzahl der Speicherplätze nur Quadratwurzel(n) - 1 + die Anzahl der Primzahlen (wenn die Primzahlen abgespeichert werden sollen) + einer konstanten Anzahl von Hilfsspeicherplätzen. Den wenigsten Speicherplatz, benötigt das Moduloverfahren (Anzahl der Primzahlen + konstante Anzahl von Hilfsspeicherplätzen), dieses ist jedoch langsamer.

(Der zugehörige Code in Java-Script befindet sich im Seitenquelltext. Einer Berechnung in einer Skriptsprache auf einer Internetseite sind natürlich Grenzen gesetzt):