Hier haben wir ein optimiertes Projekt zur Suche von Primzahlen mit der Probedivision. Dabei werden alle ungeraden Zahlen ausgehend von 3 getestet, ob sie durch eine der bereits gefundenen Primzahlen teilbar sind. Es werden alle Primzahlen zwischen 2 und der Wurzel aus der zu testenden Primzahl geprüft.
Das Verfahren beruht auf der Überlegung, dass eine nicht-prime Zahl einen kleinen Primteiler besitzt. Wir nehmen an, a sei die zu testende nicht-prime Zahl, dann sei b der kleinste Teiler von a. b ist nun prim, da es keine Zahl c gibt, für die gilt 1 < c < b und die b teilt, i.e. gibt es keinen Teiler von b. Denn ein Teiler von b wäre auch ein Teiler von a, b ist aber der kleinste Teiler von a. Somit ist bewiesen, dass jede nicht-prime Zahl durch eine kleine Primzahl teilbar ist.
Um zu beweisen, dass eine Zahl prim ist, guckt man nun, ob man einen Primteiler zu dieser Zahl findet, der kleiner als die Wurzel aus ihr ist. Dadurch, dass wir nur Primzahlen für den Test verwenden und als frühzeitiges Abbruchkriterium die Wurzel der Zahl nehmen, ist diese Suche sehr schnell.
Ich habe bei dem Projekt alle Optimierungen des Compilers angeschaltet. So wird z.b. nicht mehr geprüft, ob beim Zugriff auf ein Array der Index existent ist, oder die Genauigkeit bei Fließkommaoperationen ist nun geringer als üblich. Dies ist möglich, da wir selbst dafür sorgen, dass wir keine Fehler erzeugen, die ohne diese Optionen von VB erkannt würden. Zudem rechnen wir stets mit ganzen Zahlen, wodurch auch die Fließkommaoperationen überflüssig sind.
Auf meinem Rechner benötigt er für 10.000 Primzahlen ca. 25 Millisekunden. Athlon XP2200+
Anmerkung: Die Klasse für die Geschwindigkeitsmessung stammt von ActiveVB.
History
25.01.2003 Hinzugefügt
Autor: Dominik Auras <Dominik_auf_vbinside.de>
