JavaScripts › Mathematik

Primfaktorzerlegung

Zerlegt eine natürliche Zahl in ihre Primfaktoren und stellt sie als Produkt von Primzahlen dar — z. B. 32 = 2 · 2 · 2 · 2 · 2.

Dieses Script hat uns unser User Vollautomatisch eingeschickt — vielen Dank an dieser Stelle! Es zerlegt eine Zahl in ihre Primfaktoren, stellt sie also als Produkt aus einzelnen Primzahlen dar. Aus 32 wird so 2 · 2 · 2 · 2 · 2, aus 90 wird 2 · 3 · 3 · 5.

Die Primfaktorzerlegung ist ein Grundpfeiler der Zahlentheorie: Der sogenannte Fundamentalsatz der Arithmetik besagt, dass sich jede natürliche Zahl größer als 1 auf genau eine Weise als Produkt von Primzahlen schreiben lässt (bis auf die Reihenfolge der Faktoren). In der Schule braucht man sie etwa zum Kürzen von Brüchen oder zum Bestimmen des kleinsten gemeinsamen Vielfachen — und in der modernen Kryptographie beruht z. B. das RSA-Verfahren darauf, dass das Zerlegen sehr großer Zahlen extrem aufwendig ist.

Zur Bedienung: Tragt eine natürliche Zahl (positiv und ganzzahlig) in das Feld ein und klickt auf „In Primfaktoren zerlegen". Das Ergebnis erscheint im Ausgabefeld, neue Ergebnisse werden jeweils oben angefügt — so bleibt eine kleine Historie eurer Zerlegungen sichtbar. Ist die eingegebene Zahl selbst eine Primzahl, meldet das Script das entsprechend. Und ein nettes Extra des Autors: Lasst ihr das Feld leer oder tragt etwas Ungültiges ein, sucht sich das Script einfach selbst eine Zufallszahl bis 10.000 aus und zerlegt diese.

Passend zum Thema findet ihr im Archiv auch einen Primzahlen-Test, ein Script für die Teiler einer Zahl und den größten gemeinsamen Teiler.

Mathematik Baujahr 2007 läuft in deinem Browser

Leeres oder ungültiges Feld? Dann zerlegt das Script eine Zufallszahl bis 10.000.

Eingesandt von Vollautomatisch

So funktioniert das Script

Das Script hat zwei Herzstücke: die Funktion prim(), die prüft, ob eine Zahl eine Primzahl ist, und die Funktion primzerlegung(), die die eigentliche Zerlegung durchführt und das Ergebnis ins Ausgabefeld schreibt. Beide stecken in einer sofort ausgeführten Funktion, damit ihre Namen nicht mit anderen Scripts auf der Seite kollidieren.

function prim(zahl) {
  if (zahl === 2 || zahl === 3) {
    return true;
  }
  if (zahl < 2 || zahl % 2 === 0) {
    return false;
  }
  for (let teiler = 3; teiler <= Math.sqrt(zahl); teiler += 2) {
    if (zahl % teiler === 0) {
      return false;
    }
  }
  return true;
}

Der Primzahltest arbeitet mit dem Modulo-Operator %, der den Rest einer Division liefert: zahl % teiler === 0 bedeutet „teilbar ohne Rest". Zwei Tricks machen den Test schnell: Gerade Zahlen (außer 2) fliegen sofort raus, danach müssen nur noch ungerade Teiler geprüft werden (teiler += 2). Und die Schleife läuft nur bis Math.sqrt(zahl) — hat eine Zahl nämlich einen Teiler oberhalb ihrer Wurzel, muss der Partnerteiler unterhalb liegen und wäre längst gefunden worden.

let zahl = parseInt(document.getElementById("pfz-zahl").value, 10);

if (isNaN(zahl) || zahl < 2) {
  zahl = parseInt((Math.random() * 10000) + 1, 10);
}

const kopie = zahl;

parseInt(…, 10) macht aus dem Feldinhalt eine ganze Zahl. Steht dort nichts Brauchbares (erkannt mit isNaN(), „is Not a Number") oder etwas Kleineres als 2, wählt das Script eine Zufallszahl — das Verhalten stammt so vom Autor. In kopie wird die Ausgangszahl gesichert, denn zahl wird beim Zerlegen gleich Schritt für Schritt kleiner, für die Ausgabe brauchen wir aber noch den Originalwert.

const faktoren = [];
let i = 2;
while (i <= Math.floor(kopie / 2)) {
  if (zahl % i === 0) {
    zahl /= i;
    faktoren.push(i);
  } else {
    i++;
  }
}

Das ist die Zerlegung selbst, ein klassisches Verfahren namens Probedivision: Beginnend bei i = 2 wird geprüft, ob i die Zahl ohne Rest teilt. Wenn ja, wird durch i geteilt und der Faktor im Array faktoren gemerkt — wichtig: i wird dabei nicht erhöht, denn derselbe Primfaktor kann mehrfach vorkommen (32 enthält die 2 gleich fünfmal). Erst wenn i kein Teiler mehr ist, geht es mit i++ zum nächsten Kandidaten. Weil immer der kleinstmögliche Teiler abgespalten wird, sind alle gefundenen Faktoren automatisch Primzahlen.

ausgabe.value = kopie + " = " + faktoren.join(" * ") + "\n" + ausgabe.value;

join(" * ") verbindet alle gesammelten Faktoren zu einem Text wie 2 * 2 * 2 * 2 * 2. Die neue Zeile wird vor den bisherigen Inhalt des Ausgabefelds gesetzt — das jüngste Ergebnis steht dadurch immer oben. Am Ende des Scripts verbinden zwei addEventListener("click", …)-Aufrufe die Funktionen mit den Knöpfen; das Script steht unter dem Formular, damit alle Elemente bereits existieren.

Zum Anpassen: Das Trennzeichen der Faktoren könnt ihr in join(" * ") ändern, etwa in " · " für den Malpunkt. Wer die Zufallszahl-Spielerei bei leerer Eingabe lieber durch eine Fehlermeldung ersetzen möchte, tauscht die Zeile mit Math.random() gegen eine Meldung ins Ausgabefeld plus return.

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