JavaScripts › Mathematik

Grösster gemeinsamer Teiler

Bestimmt zu zwei Zahlen den größten gemeinsamen Teiler — die größte Zahl, durch die beide ohne Rest teilbar sind.

Das folgende Javascript berechnet euch den größten gemeinsamen Teiler zweier Zahlen — abgekürzt ggT. Für zwei ganze Zahlen a und b, die beide nicht 0 sein dürfen, gibt es immer einen solchen Teiler: die größte natürliche Zahl, durch die sowohl a als auch b ohne Rest teilbar sind. Für 84 und 132 ist das zum Beispiel die 12, denn 84 = 12 · 7 und 132 = 12 · 11.

Zur Bedienung: Tragt in die beiden Felder je eine Zahl größer als 0 ein und klickt auf „Berechnen“ — darunter erscheint sofort das Ergebnis. Ein Beispiel ist bereits vorausgefüllt, ihr könnt also gleich ausprobieren, wie sich das Ergebnis ändert, wenn ihr die Zahlen austauscht.

Gebraucht wird der ggT vor allem beim Kürzen von Brüchen: Teilt man Zähler und Nenner durch ihren größten gemeinsamen Teiler, ist der Bruch in einem Schritt vollständig gekürzt — aus 84/132 wird so direkt 7/11. Ist der ggT zweier Zahlen 1, nennt man sie teilerfremd; das spielt unter anderem in der Verschlüsselungstechnik eine Rolle. Das Script benutzt zur Berechnung den euklidischen Algorithmus, eines der ältesten bekannten Rechenverfahren überhaupt — es steht schon in Euklids „Elementen“ aus der Zeit um 300 v. Chr.

Eingereicht wurde das Javascript von einem unbekannten User. Danke an dieser Stelle! Verwandte Scripts aus derselben Kategorie: Die Teiler von zwei Zahlen listen euch alle gemeinsamen Teiler auf statt nur den größten, die Teiler einer Zahl tun dasselbe für eine einzelne Zahl, und die Primfaktorzerlegung zeigt, aus welchen Primzahlen sich eine Zahl zusammensetzt — auch daraus lässt sich der ggT von Hand ablesen.

Mathematik Baujahr 2007 läuft in deinem Browser

So funktioniert das Script

Das Script besteht aus drei kurzen Funktionen: zahl() liest ein Eingabefeld aus, ggt() rechnet, und docalc() hält beides zusammen und schreibt das Ergebnis in die Ausgabefläche. Bemerkenswert ist, wie wenig Code die eigentliche Rechnung braucht — der ganze euklidische Algorithmus passt in vier Zeilen.

function zahl(id) {
  return parseFloat(document.getElementById(id).value.replace(",", "."));
}

Diese Hilfsfunktion holt das Eingabefeld mit der angegebenen id, nimmt den eingetippten Text und macht daraus mit parseFloat() eine Zahl. Das replace(",", ".") davor tauscht ein deutsches Dezimalkomma gegen einen Punkt, denn JavaScript rechnet intern nur mit der englischen Schreibweise. Steht im Feld gar keine Zahl, liefert parseFloat den besonderen Wert NaN („not a number“).

function ggt(m, n) {
  if (n === 0) {
    return m;
  }
  return ggt(n, m % n);
}

Das ist der euklidische Algorithmus, und er ist rekursiv — die Funktion ruft sich selbst wieder auf. Die Idee dahinter: Der größte gemeinsame Teiler zweier Zahlen ändert sich nicht, wenn man die größere durch den Rest der Division ersetzt. Der Operator % liefert genau diesen Rest, 132 % 84 ergibt also 48. Aus ggT(84, 132) wird ggT(132, 84), daraus ggT(84, 48), dann ggT(48, 36), ggT(36, 12) und schließlich ggT(12, 0). Sobald die zweite Zahl 0 ist, ist die erste die Antwort — das ist die Abbruchbedingung, ohne die sich die Funktion endlos selbst aufrufen würde.

if (!(x > 0) || !(y > 0)) {
  ausgabe.textContent = "Bitte tragt in beide Felder eine Zahl größer als 0 ein.";
  return;
}

Vor der Rechnung wird geprüft. Die etwas ungewöhnliche Schreibweise !(x > 0) statt x <= 0 hat einen praktischen Grund: Sie fängt auch NaN mit ab. Vergleiche mit NaN sind nämlich immer falsch — NaN > 0 ergibt false, und das verneinte !false ist true, die Prüfung greift also. Damit werden leere Felder, Buchstaben, die Null und negative Zahlen in einem Rutsch erwischt. Statt eines alert()-Fensters wie im Original erscheint der Hinweis heute direkt in der Ergebnisfläche.

ausgabe.innerHTML =
  "Der größte gemeinsame Teiler von " + x + " und " + y +
  " ist <strong>" + ggt(x, y) + "</strong>.";

Zum Schluss wird das Ergebnis in einen ganzen Satz eingebettet. Weil hier innerHTML statt textContent benutzt wird, darf im Text HTML stehen — die <strong>-Tags heben die Zahl hervor. Das Original schrieb nur die nackte Zahl in ein <span> in einer Layout-Tabelle.

Zum Anpassen: Das Verfahren funktioniert wirklich nur bei ganzen Zahlen sinnvoll — wollt ihr Nachkommastellen von vornherein ausschließen, ersetzt parseFloat durch parseInt(…, 10); die 10 steht dabei für das Zehnersystem. Wer den Text des Ergebnissatzes oder die Fehlermeldung ändern möchte, findet beides direkt als Zeichenkette im Code. Und wer statt des ggT das kleinste gemeinsame Vielfache (kgV) braucht: Das ergibt sich aus derselben Funktion über die Formel x * y / ggt(x, y).

Script für die eigene Homepage

Kopiert euch den kompletten Code und fügt ihn an der Stelle eurer Seite ein, an der das Script erscheinen soll. Er läuft ohne weitere Dateien und ohne fremde Server.

Mehr aus der Kategorie Mathematik