vb@rchiv · Tipps & Tricks · ggT (größter gemeinsamer Teiler) zweier Ganzzahlen

Rubrik: Variablen/Strings · Algorithmen/Mathematik | VB-Versionen: VB2005, VB2008

28.08.09

ggT (größter gemeinsamer Teiler) zweier Ganzzahlen Funktion zum schnellen Ermitteln des größten gemeinsamen Teilers (ggT) zweier Ganzzahlen.
Autor: Dieter Otter	Bewertung:	Views: 15.676
www.tools4vb.de	System: Win2k, WinXP, Win7, Win8, Win10, Win11	Beispielprojekt auf CD

Nachfolgende Funktion ermittelt den größten gemeinsamen Teiler (ggT) zweier Ganzzahlen.

''' <summary>
''' Ermitteln des größten gemeinsamen Teilers (ggT) zweier Ganzzahlen
''' </summary>
''' <param name="Zahl1">Zahl1 (Ganzzahl)</param>
''' <param name="Zahl2">Zahl2 (Ganzzahl)</param>
''' <returns>ggT</returns>
Public Function ggT(ByVal Zahl1 As Integer, ByVal Zahl2 As Integer) As Integer
  ' Restwert aus Division von Zahl1 durch Zahl2
  Dim Result As Integer = Zahl1 Mod Zahl2
 
  If (Result = 0) Then
    ' bei Division ohne Rest ist die 2. Zahl der ggT
    Result = Zahl2
  Else
    ' rekursiver Aufruf der Funktion!
    Result = ggT(Zahl2, Result)
  End If
 
  ' Ergebnisrückgabe: ggT
  Return Result
End Function

Aufrufbeispiel:

' ggT aus 20 und 15 ermitteln
Dim Teiler As Integer = ggT(20, 15)
MsgBox("ggT aus 20 und 15 lautet: " & Teiler)

Anmerkung von Master of VDL
Die Lösung ist wegen der Rekursion recht Speicherintensiv und auch das Abtauchen in die Rekursion benötigt Zeit.

Effizienter wäre hier eine While-Schleife:

Dim Result as Integer = Zahl1 Mod Zahl2
 
While Result <> 0
   Zahl1=Zahl2 ' Diese Beiden Zuweisungen ersetzen den Rekursiven Aufruf
   Zahl2=Result
   Result=Zahl1 Mod Zahl2
End While
 
Return Zahl2 ' Das ist das Result=Zahl2 im THEN-Teil der If-Abfrage