Forum: Programmieren allgemein
by negaH,
24. Mär 2006
Du irrst nicht, wobei es denoch eine faszinierende Umschreibung ist :)
Einfacher gesagt: die Mathemtik die in den verschiednenen Algos. benutzt wird ist eine andere.
Die einfachste Methode ist eine Trial Division mit allen ungeraden Zahlen (und 2) von 2 beginnend bis Wurzel(N). Das Laufzeitverhalten ist das schlechteste aller verfahren und es wächst Quadratisch.
Ein leichte Abwandlung...
Forum: Programmieren allgemein
by negaH,
8. Sep 2005
Erst die schlechte Nachricht, obiger Source ist ein Cut aus meiner Contributation zum FastCode Projekt, und wie üblich: er ist fehlerhaft. Anbei also die korregierte Version. Denn ich bon stutzig geworden als du schriebst das der Test "nur" 100 mal schneller als euer sein sollte. Er sollte nämlich bei weitem schenller laufen. Am besten mal alle ungeraden Zahlen von 1 bis 2^32-1 in einer Schleife...
Forum: Programmieren allgemein
by negaH,
8. Sep 2005
Der Algo. basierst auf einem SPP = Strong Pseudo Prime Test zu festen Basen. Auf http://primes.utm.edu/prove/prove2_3.html kannst du das nachlesen.
besonders diese Passage ist interessant da sie bei meinem Algorithmus angewendet wird.
Zusätzlich wird aber ein schnellerer Test vorgschaltet der den Kandidaten zu den ersten 32 Primzahlen bis 137 testet. Es ist also eine einfache Trial...
Forum: Programmieren allgemein
by negaH,
8. Sep 2005
@Zecke:
schau dir wirklich mal den Link den ich dir gegeben habe an. Der von euch verwendetet Algorithmus ist in seiner Komplexität viel zu schlecht. Es geht also viel schneller, besonders bei großen Zahlen wird das deutlich. Probiere doch mal $FFFFFFFB aus.
Gruß Hagen
Forum: Programmieren allgemein
by negaH,
7. Sep 2005
Für eine wirklich schnelle Primzahlüberprüfung < 2^32 solltest du dir mal diese http://dennishomepage.gugs-cats.dk/IsPrimeChallenge.htm Seite anschauen.
Gruß Hagen
