Zitat von
Polynom:
Wenn ich mich nicht täusche, dann liegt die Obergrenze des Integer-Zahlenraumes in Delphi bei 2147483647.
Richtig. Da es aber keine negativen Primzahlen gibt, wäre ein Cardinal hier effizienter.
Zitat von
Polynom:
Wenn eine der Zahlen besonders klein ist, dann kann die zweite Zahl dafür umso größer sein. Wenn die erste Zahl z.B. 1 wäre, dann dürfte die zweite resultierende Primzahl bis zu 1073741821 groß werden - Ich hab nur leider keine so große Liste und kann daher nicht herausfinden welcher "normalen" Zahl dies entsprechen würde.
1 ist keine Primzahl. Ich hab mal eine Liste der ersten paar hunderttausend Primzahlen, ich könnte mal nachschauen...
Zitat von
Polynom:
Bei Hagens Methode liegt die Grenze (wenn ich das System verstanden habe und beide Zahlen etwa gleich groß sind) bei ca. 46339. (korrigiert mich, falls ich falsch liege).
Hagens Methode ist allgemein formuliert. Wenn man es im speziellen Fall für einen 32-Bit-Cardinal betrachtet, hat liegt die Grenze bei 2^16=65536.
Zitat von
Polynom:
An diesem Punkt bin ich etwas verwirrt: Angenommen eine der beiden Zahlen sei enorm klein. Wenn ich die Aussage von Hagen genau so auffasse, wie sie dasteht, dann würde das bedeuten, dass die andere Zahl nur geringfügig größer werden kann. Dies würde dann bei weit auseinander liegenden Zahlen fast schon für die Primzahl-Methode sprechen.
Wie gesagt - Hagens Methode war allgemein. Bei sehr weit auseinanderliegenden Zahlen kann eine Zahl bei der Primzahlmethode tatsächlich größer sein. Dafür ist die Primzahlmethode äußerst ineffizient.
Zitat von
Polynom:
Zum Zeitaufwand bei der Primzahl-Methode: Ich gebe zu, dass der Zeitaufwand für eine Primfaktorzerlegung recht hoch ist, aber ich weiß leider nicht für welches Anwendungsgebiet dies verwendet werden soll. Programme zur Zerlegung in Primfaktoren brauchen bei mir etwa 350 ms für Zahlen im Bereich von 46337*46337. Falls dies auf mehreren Zahlen angewendet wird, so sehe ich es ein, dass der Zeitaufwand nicht akzeptabel wäre.
Die Angabe einer Zeit ist bei Algorithmen nicht aussagekräftig, da sie vom Compiler, dem Betriebssystem, den laufenden Prozessen/Threads und dem Rechner abhängt. Wie bereits gesagt, ein Primzahltest der Zahl n geht in der Zeit O(sqrt(n)), was für kleinere Zahlen keine wirklich schlechte Laufzeit ist, aber Hagens Methode geht in konstanter Zeit und ist damit selbstverständlich zu bevorzugen.