Feedback

Effizientere Primzahlprüfung großer Zahlen

VB - Klemens Nanni April 7, 2010
0 Ratings 0/5

Sprache: VB

Mit dieser Funktion lässt sich eine Menge großer Primzahlen weitaus schneller berechnen. Zum Vergleich: [u]Slow[/u]: 664579 primes < 10^7 computed in [b]00:08.6306629[/b] [u]Fast[/u]: 664579 primes < 10^7 computed in [b]00:05.2659327[/b] [u]Slow[/u]: 5761455 primes < 10^8 computed in [b]04:52.4940141[/b] [u]Fast[/u]: 5761455 primes < 10^8 computed in [b]03:07.4373887[/b] mm:ss.ms
Function Slow(ByVal n As Integer) As Boolean
    If n Mod 2 = 0 OrElse n Mod 3 = 0 OrElse n Mod 7 = 0 OrElse n Mod 5 = 0 Then Return False

    For i As Short = 11 To Math.Sqrt(n) Step 2
        If n Mod i = 0 Then Return False
    Next

    Return True
End Function

Function Fast(ByVal n As Integer) As Boolean
    If n Mod 2 = 0 OrElse n Mod 3 = 0 OrElse n Mod 7 = 0 OrElse n Mod 5 = 0 Then Return False

    Dim r As Single = Math.Sqrt(n), f As Short = 11
    If r Mod 1 = 0 Then Return False

    While f <= r
        If n Mod f = 0 Then Return False
        f += 2
        If n Mod f = 0 Then Return False
        f += 4
    End While

    Return True
End Function
Function Slow(ByVal n As Integer) As Boolean
    If n Mod 2 = 0 OrElse n Mod 3 = 0 OrElse n Mod 7 = 0 OrElse n Mod 5 = 0 Then Return False

    For i As Short = 11 To Math.Sqrt(n) Step 2
        If n Mod i = 0 Then Return False
    Next

    Return True
End Function

Function Fast(ByVal n As Integer) As Boolean
    If n Mod 2 = 0 OrElse n Mod 3 = 0 OrElse n Mod 7 = 0 OrElse n Mod 5 = 0 Then Return False

    Dim r As Single = Math.Sqrt(n), f As Short = 11
    If r Mod 1 = 0 Then Return False

    While f <= r
        If n Mod f = 0 Then Return False
        f += 2
        If n Mod f = 0 Then Return False
        f += 4
    End While

    Return True
End Function
Abgelegt unter check integer number prime Primzahl proof prüfen Zahl

Alte URL: /snippet/effizientere-primzahlpruefung-grosser-zahlen/1373

3 Kommentare

  1. … schöne Sache.
    Ausser das die Bedingung „5 = 0“ nie zutrifft.
    Müsste das dann nicht eher „n Mod 5 = 0“ sein ?

    Also so…
    [code]
    Function Slow(ByVal n As Integer) As Boolean
    If n Mod 2 = 0 OrElse n Mod 3 = 0 OrElse n Mod 7 = 0 OrElse[b] n Mod 5 = 0 [/b]Then Return False

    For i As Short = 3 To Math.Sqrt(n) Step 2
    If n Mod i = 0 Then Return False
    Next

    Return True
    End Function

    Function Fast(ByVal n As Integer) As Boolean
    If n Mod 2 = 0 OrElse n Mod 3 = 0 OrElse n Mod 7 = 0 OrElse [b]n Mod 5 = 0 [/b]Then Return False

    Dim r As Short = Math.Sqrt(n), f As Short = 5
    While f <= r If n Mod f = 0 OrElse n Mod (f + 2) = 0 Then Return False f += 6 End While Return True End Function[/code] Lg Firen

  3. die Funktion ‚Fast‘ wurde durch [b]Zeile 15[/b] nochmals beschleunigt. Denn ist die Wurzel eine natürliche Zahl, so hat n mehr als zwei Teiler & kann keine Primzahl sein.