Primzahlen in VBA ausrechnen?

anfänger_engel

Also ich habe jetzt eine Funktion gemacht mit der ich Primzahlen ermitteln kann und ich gehe mal davon aus, dass sie stimmt...(siehe weiter unten...)
Mein eigentliches problem ist, wie kann ich die Funktion Prim() beschleunigen, indem nicht so viel unnütz gesucht wird?
Muss bei der Untersuchung, ob 197 eine Primzahl ist, wirklich getestet werden, ob 196 ein Teiler ist?
Wie groß kann der größte echte Teiler denn höchstens sein?
Kann vielleicht noch ein bisschen „früher“ festgestellt werden, dass es gar keinen echten Teiler gibt und die Zahl daher eine Primzahl ist?

Option Explicit
Function IstPrim(zahl As Integer) As Boolean
Dim i As Integer
IstPrim = True
If zahl <= 1 Then
IstPrim = False
Else
If (zahl Mod 2) = 0 Then 'Gerade Zahl
IstPrim = False
Else 'Ungerade Zahl
For i = 3 To zahl - 1
If (zahl Mod i) = 0 Then 'Teiler i gefunden
IstPrim = False
End If
Next
End If
End If
End Function

Bitte um Hilfe! Ich möchte auch irgendwann einmal ein Profi sein

Trux

Zitat von anfänger_engel

Muss bei der Untersuchung, ob 197 eine Primzahl ist, wirklich getestet werden, ob 196 ein Teiler ist?

nein. du musst nur bis zur wurzel der zahl gehn

Ringding

Eher bis zur Wurzel.

viper

Zitat von anfänger_engel

wie kann ich die Funktion Prim() beschleunigen, indem nicht so viel unnütz gesucht wird?

Dafür gibt es einige Ansätze (siehe z.B. http://de.wikipedia.org/wiki/Primzahltest), die mit mehr oder weniger Aufwand verbunden sind.

Zitat

Wie groß kann der größte echte Teiler denn höchstens sein?

Der größte mögliche Teiler einer Zahl p (außer p selbst) ist [tex='\lfloor\sqrt{p}\rfloor'][/tex]

, d.h. die größte ganze Zahl, die kleiner oder gleich die Wurzel von p ist.
Eine andere Schranke (wenn du sqrt() nicht aufrufen willst), ist [tex='\frac{p}{2}'][/tex]

.

Du kannst deinen Algorithmus auch beschleunigen, indem du z.B. gerade Zahlen größer als 2 beim Test überspringst (also bei 61 würdest du 2, 3, 5 und 7 probieren, aber nicht 4 oder 6). Im Allgemeinen kann man alle Zahlen, die keine Primzahlen sind, überspringen; jedoch müsste man dafür schon eben eine Liste von Primzahlen haben, auf der man schnell zugreifen kann.

Jetzt mitmachen!