Primzahlen in VBA ausrechnen?

Hallo zusammen,

das Informatik-Forum geht in den Archivmodus, genaue Informationen kann man der entsprechenden Ankündigung entnehmen. Als Dankeschön für die Treue bekommt man von uns einen Gutscheincode (informatikforum30) womit man bei netzliving.de 30% auf das erste Jahr sparen kann. (Genaue Infos sind ebenfalls in der Ankündigung)

Vielen Dank für die Treue und das Verständnis!

    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 ^^

    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.