vb@rchiv · Tipps & Tricks · Primzahlen ermitteln

Rubrik: Variablen/Strings · Algorithmen/Mathematik | VB-Versionen: VB4, VB5, VB6

01.10.01

Primzahlen ermitteln - optimiert Diese Routine zeigt, wie man alle Primzahlen bis zu einer bestimmten Zahl ermitteln kann.
Autor: Baar Lun	Bewertung:	Views: 21.378
ohne Homepage	System: Win9x, WinNT, Win2k, WinXP, Win7, Win8, Win10, Win11	Beispielprojekt auf CD

Die nachfolgende Funktion ermittelt alle Primzahlen bis zu einer bestimmten Zahl und gibt diese als String-Variable zurück.
Zur Info: Primzahlen sind Zahlen, die nur durch 1 und durch sich selber teilbar sind, z.B. 3,5 oder 7.

' Alle Primzahlen bis BisZahl ermitteln
Private Function GetPrimzahlen(BisZahl As Integer) As String
  Dim keinePrim As Boolean
  Dim m As Integer
  Dim n As Integer
  Dim t As Integer
  Dim Primzahlen As String
 
  ' Herausfiltern der Primzahlen
  ' Alle ungeraden Zahlen durchzählen
  For n = 3 To BisZahl Step 2
    keinePrim = False
    m = sqr(n) 
    ' Testen ob die Zahl einen Teiler hat.
    For t = 3 To m Step 2
      If n Mod t = 0 Then
        ' Zahl hat einen Teiler, also keine Primzahl
        keinePrim = True
        Exit For
      End If
    Next t
    m = n + 1
    If Not keinePrim Then _
      Primzahlen = Primzahlen & " " & n
  Next n
  GetPrimzahlen = Primzahlen
End Function

Im Gegensatz zu unserem früheren Tipp zur Ermittlung der Primzahlen, ist die Funktionsweise der obigen Routine um ein Vielfaches optimiert worden, da:

Der größte Teiler einer Zahl kann nur die Wurzel dieser Zahl sein, da sonst wieder ein Teiler "auftaucht", der schon geprüft wurde:

Bsp. 100
Teiler 5 :  100 /  5 = 20
Teiler 20:  100 / 20 =  5

Somit:

Teiler sqr(100) = 10 : 100 / 10 = 10

Deshalb braucht m nur bis wurzel(n) zu zählen und nicht bis n-1. Dies spart enorm Zeit, wenn man den Bereich der Primzahlen auf Long ausdehnt.