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>

---

Download (ZIP)

Code aus: Form1.frm, xTimer.cls

Code aus xTimer.cls
Option Explicit
Private Declare Function QueryPerformanceCounter Lib "kernel32" _
    (lpPerformanceCount As LARGE_INTEGER) As Long
Private Declare Function QueryPerformanceFrequency Lib "kernel32" _
    (lpFrequency As LARGE_INTEGER) As Long
Private Type LARGE_INTEGER
  Lo As Long
  Hi As Long
End Type
Dim Strt As LARGE_INTEGER
Dim Ende As LARGE_INTEGER
Dim Freq As LARGE_INTEGER
Dim Calibr As Double
Private Sub Class_Initialize()
    Call QueryPerformanceFrequency(Freq)
End Sub
Public Sub Calibrieren()
    Call QueryPerformanceCounter(Strt)
    Call QueryPerformanceCounter(Ende)
    Calibr = (D(Ende) - D(Strt)) / D(Freq) * 1000
    'ms
End Sub
Public Sub Start()
    Call QueryPerformanceCounter(Strt)
End Sub
Public Sub Halt()
    Call QueryPerformanceCounter(Ende)
End Sub
Public Property Get RunTime() As Variant
'ms
RunTime = (D(Ende) - D(Strt)) / D(Freq) * 1000 - Calibr
End Property
Private Function D(x As LARGE_INTEGER) As Double
Dim l As Double, h As Double
l = x.Lo
h = x.Hi
If l < 0 Then
  l = 4294967296# + l + 1
End If
If h < 0 Then
  h = 4294967296# + h + 1
End If
D = l + h * 4294967296#
End Function