Sehr schneller Primzahl-Finder

[alzaimar]

Falls es hier jemanden interessiert: Ich habe mal PrimeGen, genauergesagt nur den FastSieve.c Code, in Delphi implementiert: Alle Primzahlen bis 500.000.000 (genau : 500.660.190) findet der in 840ms. Pentium M 1.5GHz. Kein Assembler, nur Delphi, aber mit Pointern statt Array-Zugriffen (Sonst 1200ms).

Naja, um genau zu sein, erstellt er 'nur' das Sieb.

Ich habe mir nicht die Mühe gemacht, den Code so humzufrickeln, das er alle Primzahlen bis genau 500 Mio findet. PrimeGen berechnet immer einen Block von 960960 Zahlen. Ich habe den Code so original wie möglich belassen. Der Code ist aber (eben) C-Code, bei dem handoptimiert (d.h Register-Variablen etc.) wurde, das musste natürlich weg. Egal. Der Code benutzt die ersten 3509 Primzahlen als Konstante, was vielleicht geschummelt ist, aber ich denke, wenn man das berechnen würde, dürfte das die Performance nicht runterziehen.

Offensichtlich muss man keinen hochoptimierenden Assemblercode mehr schreiben, um schnellen Code zu erzeugen.

Code kann jeder selbst basteln (nach 'sieve of atkins' und/oder PrimeGen googeln und den Source suchen').

Hier ist mein Testprogramm: