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>
Code aus Form1.frm
Public Function PrimzahlenSuche(count As Long) As Variant
Dim Primzahlen() As Long, p As Long, cnt As Long
Dim i As Long, ub_Prim As Long, ret As Long
Dim Wurzel As Long
ReDim Primzahlen(count - 1)
Primzahlen(0) = 2
cnt = 1
ub_Prim = 0
p = 3
While cnt < count
Wurzel = Int(Sqr(p)) + 1
For i = 0 To ub_Prim
ret = p Mod Primzahlen(i)
If ret = 0 Then
Exit For
End If
If Primzahlen(i) > Wurzel Then
Exit For
End If
Next i
If ret <> 0 Then
ub_Prim = ub_Prim + 1
Primzahlen(ub_Prim) = p
cnt = cnt + 1
End If
p = p + 2
Wend
PrimzahlenSuche = Primzahlen
End FunctionPublic Function PrimzahlenSuche_Limit(limit As Long) As Variant
Dim Primzahlen() As Long, p As Long, cnt As Long
Dim i As Long, ub_Prim As Long, ret As Long
Dim Wurzel As Long
ReDim Primzahlen(100000)
Primzahlen(0) = 2
cnt = 1
ub_Prim = 0
p = 3
While p <= limit
Wurzel = Int(Sqr(p)) + 1
For i = 0 To ub_Prim
ret = p Mod Primzahlen(i)
If ret = 0 Then
Exit For
End If
If Primzahlen(i) > Wurzel Then
Exit For
End If
Next i
If ret <> 0 Then
ub_Prim = ub_Prim + 1
If UBound(Primzahlen) < ubprim Then
ReDim Preserve Primzahlen(UBound(Primzahlen) + 100000)
End If
Primzahlen(ub_Prim) = p
cnt = cnt + 1
End If
p = p + 2
Wend
ReDim Preserve Primzahlen(cnt - 1)
PrimzahlenSuche_Limit = Primzahlen
End Function
Private Sub Command1_Click()
Dim Primzahlen() As Long, i As Long, xTime As New xTimer
xTime.Calibrieren
xTime.Start
Primzahlen = PrimzahlenSuche(10000)
xTime.Halt
Label1.Caption = UBound(Primzahlen) + 1 & " Primzahlen " & _
Format(xTime.RunTime, "0.000000 ms")
List1.Clear
For i = 0 To UBound(Primzahlen)
List1.AddItem Primzahlen(i)
Next i
End Sub
Private Sub Command2_Click()
Dim Primzahlen() As Long, i As Long, xTime As New xTimer
xTime.Calibrieren
xTime.Start
Primzahlen = PrimzahlenSuche_Limit(10 ^ 6)
xTime.Halt
Label1.Caption = UBound(Primzahlen) + 1 & " Primzahlen " & _
Format(xTime.RunTime, "0.000000 ms")
List1.Clear
For i = 0 To UBound(Primzahlen)
List1.AddItem Primzahlen(i)
Next i
End Sub
