PrimNum

PrimNum ist ein kleines Programm das Primzahlen zwischen 1 - 1'000'000'000 mit einem sehr schnellen Algorithmus berechnet.
Je nach Prozessor können die bis zu Primzahl 1'000'000'007, 50'847'536 Zahlen in zwischen 20 - 60 Sekunden berechnet werden. Dabei ist die Zeitkomplexität fast linear. Es ist komplett in Visual-Basic geschrieben, würde man die Kern-Routinen in ASM programmieren, könnte man die Geschwindigkeit noch weiter steigern. Werden die Zahlen gleichzeitig gespeichert dauert die Berechnung um einiges länger. Aber Vorsicht, die Datei kann dabei 527MB groß werden.
Der Algorithmus basiert auf dem Sieb-des-Eratosthenes, statt bei jeder Zahl alle ungeraden Zahlen bis zu Sqr(P) zu prüfen kann ein ganzes Segment an Zahlen bearbeitet werden und das hauptsächlich nur mit Additions-Operationen.
Das Programm kann sozusagen als platzsparenden Listengenerator benutzt werden für diejenigen die eine solche zum testen brauchen, können sie die in beliebiger Länge generieren ohne die Liste selbst aufbewahren zu müssen.

Die Zeitmessungen wurden mit einem 933MHz CPU und einer langsamen Harddisk gemessen. Nicht alle Prozessoren bearbeiten gleiche Operationen auch gleich schnell, so kann es sein das auch ein schnellerer Prozessor langsamer ist weil ein anderer bestimmte Funktionen effizienter durchführt, zB. Byte Long oder Array Operationen.
(Hinweis: Per Definition ist 1 aus mathematischen Gründen keine Primzahl, dennoch ist 1 unteilbar und steht deshalb auf der Liste.)

Das Programm ist Freeware und liegt im Download.