Forum: Programmieren allgemein
by alzaimar,
24. Mär 2006
Genau. Das ist ja schon mal etwas langsamer, als meine Version, die nur die Zahlen der Form 6n+/-1 prüft. Hagen verwendet jedoch einen völlig anderen Algorithmus.
Es gibt Prüfungen, die sehr sehr schnell erkennen, ob eine Zahl KEINE Primzahl ist. Wenn der Test fehlschlägt, heisst das noch nicht, das die Zahl eine Primzahl ist, aber immerhin. Dieser Test hat einen zweiten Parameter (A und B)....
Forum: Programmieren allgemein
by alzaimar,
24. Mär 2006
Na, das Verfahren. Was sonst. Oder wie rechnest du das aus?
Forum: Programmieren allgemein
by alzaimar,
23. Mär 2006
Das würde ich aber mal tun, den Deine ist sogar langsamer als meine primitive Funktion ('IsPrime'). Vorausgesetzt, man ersetzt Int64 durch Cardinal.
Forum: Programmieren allgemein
by alzaimar,
8. Sep 2005
Ich wollte schon den Fermat-Test vorschalten, aber scheiterte eben an diesem a^n mod (n-1)... Da hat Montogomery wohl einen Trick gefunden, sehe ich das richtig? Ich finde das wirklich sehr spannend und würde liebend gern meine Zeit mit solchen Geschichten verbringen, aber was mach ich? Projekte durchziehen, Beratung, etc... Man kann nicht Alles haben.
Auf jeden Fall danke für die Info.
...
Forum: Programmieren allgemein
by alzaimar,
8. Sep 2005
EDIT:
Ich würde aber trotzdem das 'Sieve of Atkins' in der Implementierung von negaH nehmen und einfach schauen, ob das entsprechende Bit gesetzt ist. Googel mal danach oder suche hier im Forum. Da gab es vor Kurzem einen lustigen Thread.
Forum: Programmieren allgemein
by alzaimar,
8. Sep 2005
Bei mir erscheint auch der Test mit 2147483647 ohne Verzögerung (also nach 0ms). Allerdings benutze ich ein anderes Verfahren:
Ich prüfe nicht alle Zahlen bis N / 2, sondern nur bis s=Sqrt(N). Denn eine Zahl N kann nur Primfaktoren haben, die <=s sind.
Dann kann man noch die Tatsache ausnutzen, das für alle Primzahlen P > 3 gilt: P modulo 6 = 1 oder 5.
Function IsPrime (aNumber : Int64) :...
