Feedback
dotnet-snippets.de

VB - Effizientere Primzahlprüfung großer Zahlen

Veröffentlicht von am 4/7/2010
(0 Bewertungen)
Mit dieser Funktion lässt sich eine Menge großer Primzahlen weitaus schneller berechnen. Zum Vergleich:

Slow: 664579 primes < 10^7 computed in 00:08.6306629

Fast: 664579 primes < 10^7 computed in 00:05.2659327

Slow: 5761455 primes < 10^8 computed in 04:52.4940141

Fast: 5761455 primes < 10^8 computed in 03:07.4373887

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
Abgelegt unter Primzahl, prime, prüfen, proof, check, Zahl, Number, Integer.

3 Kommentare zum Snippet

Firendeath schrieb am 4/9/2010:
... schöne Sache.
Ausser das die Bedingung "5 = 0" nie zutrifft.
Müsste das dann nicht eher "n Mod 5 = 0" sein ?

Also so...

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 = 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 n Mod 5 = 0 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


Lg Firen
Klemens Nanni schrieb am 4/9/2010:
Jup, ist ein Tippfehler gewesen. Danke (:
Klemens Nanni schrieb am 4/15/2010:
die Funktion 'Fast' wurde durch Zeile 15 nochmals beschleunigt. Denn ist die Wurzel eine natürliche Zahl, so hat n mehr als zwei Teiler & kann keine Primzahl sein.
 

Logge dich ein, um hier zu kommentieren!

Ähnliche Snippets

Suche

Letzte Kommentare