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]

C# 2017/2015/2013 Aufbau

In dieser Schulung lernen Sie fortgeschrittene Techniken im Bereich .Net C#. Dabei stehen neben den eigentlichen Techniken auch architektonische Aspekte im Mittelpunkt.

VB.NET 2017/2015/2013 Aufbau

Nach dieser Schulung können Sie mittels objektorientierter Modelle in VB.NET 2017/2015/2013 wiederverwendbare Elemente eigenständig erstellen.

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!