Primzahlen berechnen

Vor wenigen Tagen bekam ich eine (größere) Primzahl mit 91 Stellen vorgelegt.

Das weckte meinen Ehrgeiz: Bis zu welcher Größe kann man denn auf einem RaspberryPi und mit Python Primzahlen im Sekundenbereich berechnen/finden oder bestätigen?

In meinen Tests konnte ich für Zahlen bis 1.000.000.000.000 relativ locker ausprobieren, ob es sich um eine Primzahl handelt oder nicht, bei 3 Nullen mehr sollte ich mir dann einen Kaffee gönnen ……

Das „Sieb des Eratosthenes“ gelingt auf dem Raspberry bis 9.999.999 recht gut, die erzeugte Liste hat dann 664579 Primzahlen und benötigt ungefähr 40 MByte Speicher. Damit kann man bequem 7-stellige Zahlen in ihre Primfaktoren zerlegen oder 14-stellige Primzahlen testen. Und auch ein Laie wie ich kann den Ansatz nachvollziehen.

Falls man mal eine Primzahl braucht, kann man mit diesen einfachen Verfahren einen Bereich von Zahlen testen und findet dann auch relativ schnell eine Primzahl im gewünschten Größenbereich.

Allerdings fehlen mir immer noch gut 70 Stellen zur vorgegebenen Primzahl ….

Vielleicht sollte ich mich mal mit speziellen Verfahren für größere Primzahlen beschäftigen. Zum Beispiel mit Mersenne-Primzahlen und dem dazu passenden Lucas-Lehmer-Test.

Print Friendly, PDF & Email