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 Einführung

Die Schulung zeigt Ihnen, wie Sie einfache, benutzerorientierte Programme, die auf Datenbanken zugreifen, in VB.NET eigenständig entwickeln. 

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!