Feedback

VB - Effizientere Primzahlprüfung großer Zahlen

Veröffentlicht von am 07.04.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
GFU-Schulungen  [Anzeige]

Visual Studio Team Foundation Server 2017/2015 (TFS) für Projektmitglieder - Kompakt

Nach Teilnahme an dieser Schulung sind Ihnen die Grundlagen von ALM geläufig. Sie planen und steuern Projekte effizient mit dem Visual Studio Team Foundation Server.

VB.NET Aufbau

Sie verfügen nach der Schulung über fundierte Kenntnisse in der Arbeit mit objektorientierten Modellen in VB.NET und können wiederverwendbare Komponenten eigenständig erzeugen.

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 09.04.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 09.04.2010:
Jup, ist ein Tippfehler gewesen. Danke (:
Klemens Nanni schrieb am 15.04.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!