Sieben

Aus Rechenkraft
Zur Navigation springen Zur Suche springen

Viele Primzahlprojekte koordinieren einen Siebvorgang. Dieser dient dazu, in einem bestimmten Bereich alle Zahlen zu entfernen, die auf keinen Fall eine Primzahl sein können und daher nicht getestet werden müssen. Diese Zahlen fallen quasi durch das Sieb. Die Idee ist die, dass das Sieb alle Zahlen auf Teiler untersucht. Dabei wird geprüft, ob die Zahlen durch 2 und dann, ob sie durch 3,5,7,11 usw. teilbar sind. Auf diese Weise werden alle Zahlen im gewünschten Bereich durch Primzahlen in aufsteigende Reihenfolge geteilt. Dies ermöglicht es in relativ kurzer Zeit eine große Anzahl an Werten zu eliminieren. Das Prinzip, das Sieb des Eratosthenes, wird genauer in der Wikipedia erklärt.

Zahlen die keine Primzahlen sein können, sind z.B. alle geraden Zahlen. Die Form der Primzahlen hängt von dem Projekt ab, so sucht Riesel Sieve nach Primzahlen der Form k · 2n - 1 wohingegen das Prime Sierpinski Project die Form k · 2n + 1 sucht. Das heißt, diese Projekte sieben alle Zahlen, die sich durch Kombinationen von den verbliebenen k-Werten und allen n-Werten bis zu einer bestimmten Grenze ergeben.

Wenn nun bei einem dieser beiden Projekte eine Primzahl für ein bestimmtes k gefunden wird, werden auf einen Schlag alle n-Werte für dieses k aus dem Sieb geworfen. Das liegt daran, dass diese Projekte für jedes k nur eine Primzahl finden wollen, evtl. fallen so weitere Primzahlen durch das Sieb.

Es gibt noch mit unterschiedlichen Zielsetzungen und Primzahl-Formen.

Für Zahlen, für die bei einem Siebvorgang kein Faktor gefunden wurde, muss entweder durch weiteres Sieben mit einem größeren Bereich nach Faktoren gesucht werden, oder sie müssen später noch einzeln überprüft werden.

Ewig Sieben?

Eine Frage, die sich hierbei stellt ist, wie lange man Sieben will / muss. Durch das Sieben werden zwar viele Tests eliminiert, aber keine Primzahlen gefunden. Idealerweise sollte man den Siebvorgang beenden, wenn es länger dauert einen Faktor durchs Sieben zu finden, als die Zahlen einem Primzahltest zu unterziehen.

Die Projekte weichen davon allerdings etwas ab, da sie jede Zahl 2 mal testen um sicherzustellen, dass die Berechnung fehlerfrei war. Sie sieben daher noch länger, da ein gefundener und übermittelter Faktor direkt und in kürzester Zeit vom Server überprüft wird und somit eindeutig einen Kandidaten aus der Datenbank löscht. Diese direkte Überprüfung sorgt dafür, dass ein Kandidat für den ein Faktor übermittelt wurde, keinen weiteren Test benötigt bzw. der Faktor als 2. Test für einen bereits überprüften Wert zählt.

Ende des Siebs abschätzen

Mit 3 Variablen kann man grob ausrechen, wie lange es dauert einen Faktor zu finden. Man benötigt

  1. p = Fortschritt des Siebvorgangs (größter schon ausprobierter Faktor)
  2. n = Anzahl der Kandidaten im Sieb (nach Sieben bis zum Faktor p)
  3. s = Geschwindigkeit des Siebprogramms (in p/sec)

Damit errechnet man, wie viele Sekunden man etwa pro gefundenen Faktor Sieben muss:

Sieben1.gif.

Für die Berechnung, wie viele Faktoren ungefähr in dem Bereich von pmin bis pmax gefunden werden, bietet sich folgende Formel an:

Sieben2.gif.

Generell sind AMD-Prozessoren schneller was das Sieben angeht, als Intel-Prozessoren. Dafür eignen sich die Letztgenannten mehr für die Primzahltests.

Sieb-Programme

Links