Primzahlen finden

Rechner, der alle Primzahlen in einem vorher festgelegten Wertebereich ausgibt. Eine Primzahl ist eine natürliche Zahl, die nur durch 1 und sich selbst teilbar ist. Primzahlen spielen eine wichtige Rolle in der Zahlentheorie und in der Kryptographie. Für den letzteren Bereich braucht man allerdings sehr große Primzahlen, hier können nur Zahlen bis zu maximal 10¹⁵ berechnet werden. Das sind Zahlen unter einer Billiarde. Die Kryptographie arbeitet mit noch größeren Werten.

Beispiel: die Primzahlen zwischen 180 und 200 sind: 181 191 193 197 199

Bei einer großen Spanne oder sehr hohen Zahlen kann die Berechnung durchaus eine Weile dauern.

Eine bekannte antike Methode zum Auffinden von Primzahlen ist der Sieb des Eratosthenes. Diese Methode eines Zahlensiebs wird hier nicht verwendet. Wenn man die Primzahlen in einem beschränkten Intervall mit einer von 1 merklich entfernten Untergrenze sucht, dann ist dieser Sieb nicht sehr effektiv. Hier wird für jede Zahl im angegebenen Intervall getestet, ob sie durch ganzzahlige Werte zwischen 2 und der Wurzel dieser Zahl teilbar ist. Wenn ein solcher Teiler gefunden wird, dann bricht der Algorithmus ab, wenn er dagegen bis zum Ende durchläuft und nichts findet, dann wird der Wert als Primzahl ausgegeben. Dies ist die gängige Methode um eine Zahl auf die Primzahleigenschaft zu testen. Für große Zahlen muss dabei sehr viel gerechnet werden, daher dauert es für diese auch so lange. Das gibt der Kryptographie ihre Sicherheit. Diese basiert oft auf dem Produkt zweier sehr großer Primzahlen, was natürlich eine noch viel größere Zahl ist. Diese Zahl wiederum zu faktorisieren, sie also in ihre beiden Primfaktoren zu zerlegen, ist mit den schnellsten Computern noch nicht in sinnvoller Zeit möglich.

Siehe auch Primfaktorzerlegung um eine Zahl in Primzahlen zu zerlegen, welche miteinander multipliziert eben diese Zahl ergeben.