Zahl auf Primzahl prüfen

[Codewalker]

Mit dem Fermat muss man vorsichtig sein, wie man ihn einsetzt: Man kann damit nur zeigen, dass eine Zahl i keine Primzahl ist, also einen Gegenbeweis finden. Die Umkehrung gilt nicht (genauer: Sie gilt nicht für alle Carmichael-Zahlen wie 561, 1105, usw)!

Je nachdem um was es geht reicht aber auch ein probabilistischer Primzahltest. Mit diesem macht man eine bestimmte Anzahl Iterationen und kann dann mit einer gewissen Genauigkeit sagen, dass eine Zahl i eine Primzahl ist (oder halt exakt sagen, dass sie keine ist, wenn man einen Teiler findet). Nimmt man beispielsweise den Miller-Rabin-Test (ist nicht allzu aufwändig zu implementieren), so hat man nach 33 Iterationen eine Fehlerquote < 10^⁻100 (d.h. man kann 10^100 Primzahlen auf diese Weise ermitteln und macht statistisch dann den ersten Fehler. Da ist mehr als es Atome im Universum gibt, dürfte aber reichen). Wenn man eine brauchbare BigInteger-Unit nimmt, ist die Rechnung auch ordentlich performant.

Wenn es bei den vom TE genannten kleinen Zahlen bleibt, ist aber auch ein stures durchprobieren aller Teiler immer noch hinreichend schnell.

@DeddyH: Du fängst in deinem Code bei Pred(a) an, was unnötig ist. Damit es ein Teiler ist, kann er ja maximal halb so groß sein wie a. Man kann auch zeigen, dass es reicht bis zur Quadratwurzel von a durchzuprobieren. Damit sparst du nochmal etliche Durchläufe.