Hallo
Kann mir jemand sagen, wie ich eine grosse Zahl(>50 Stellen) unter TP/Delphi prüfen kann, ob sie eine Primzahl ist oder nicht.
Meine jetzige Lösung (die Zahl wird als array of [0..9] abgelegt/verarbeitet) funktioniert zwar, aber bereits bei einer 20 stelligen Zahl dauert es mehrere Stunden!!!
Besonders die benötigte mod Funktion benötigt so lange.
Vielen Dank für Euer Bemühen!
lari
Hallo!
Du hast zwar nicht geschrieben, welche Testmethode Du verwendest, aber wenn Du einfach nur alle (ungeraden) Zahlen nacheinander als Teiler abklapperst (bis zur Quadratwurzel aus der zu testenden Zahl), dann bekommst Du schnell ein Problem mit der Rechenzeit. Zum Glück gibt es aber schnelle Primzahltest-Algorithmen". Man braucht sie z. B. bei den Public-Key-Verschlüsselungsverfahren, wo die Schlüssel bekanntlich riesengroße Primzahlen sind. Ein Generator für solche Zahlen ezeugt erst einmal irgendeine riesengroße Zahl (per Zufallsgenerator) und testet sie anschließend auf "Primheit".
Das Stichwort lautet "probabilistischer Primzahltest", und mehr dazu erfährst Du unter
http://www.rhein-neckar.de/~karolinc/monoid/primrabi...
und
http://www.mathematik.uni-muenchen.de/~forster/kk/pr...
Viel Spaß!
Martin
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hi zusammen!
Das Stichwort lautet "probabilistischer
Primzahltest", und mehr dazu erfährst Du
unter
http://www.rhein-neckar.de/~karolinc/monoid/primrabi...
und
http://www.mathematik.uni-muenchen.de/~forster/kk/pr...
Erstmal danke an Martin, daß er so gute Tips hat. Das muß ich mir auch unbedingt anschaun.
Zweitens: Ich hab eine Unit für FPC geschrieben, mit der man mit riesengroßen Zahlen (bis ca. 10^608 als Ganze Zahlen) rechnen kann. Dabei is auch ein Primzahlentest. Den hab ich nach einen Tip aus dem Mathematik&Physik-Board. Der is schneller, als einfach nur durchprobieren. Diese Unit kann ich Dir am Sonntag abend Mailen, wenn Du sie haben willst. Is noch sehr einfach, aber der Primzahlentest tut schon einiges. Dauert noch lange, aber sicher schneller, als Deiner! :-)
Diese hier angegebenen Methoden muß ich erst noch anschaun, vielleicht bau ich das mal ein, wenn ich mehr Zeit habe.
Bye
Hansi