Was ist die Primfaktorzerlegung einer Zahl?

Die Primfaktorzerlegung schreibt eine Zahl als Produkt ihrer Primfaktoren, zum Beispiel 60 = 2² × 3 × 5. Nach dem Fundamentalsatz der Arithmetik ist diese Zerlegung für jede Zahl größer als 1 eindeutig, abgesehen von der Reihenfolge der Faktoren.

Wie prüfe ich schnell, ob eine Zahl eine Primzahl ist?

Bei kleinen Zahlen reicht die Probedivision: teste, ob die Zahl durch eine ganze Zahl von 2 bis zu ihrer Quadratwurzel glatt teilbar ist. Bei großen Zahlen (viele Stellen) wird das per Hand unpraktisch; der ToolPico-Rechner nutzt dafür automatisch einen schnellen Miller-Rabin-basierten Test und liefert das Ergebnis sofort.

Wie finde ich alle Teiler einer Zahl?

Zerlege die Zahl zuerst in Primfaktoren und bilde dann alle möglichen Kombinationen dieser Faktoren mit ihren Exponenten. Für 12 = 2² × 3 ergeben sich so die Teiler 1, 2, 3, 4, 6 und 12 — insgesamt sechs Stück. Der Rechner listet diese Teiler automatisch mit auf, sobald du eine Zahl eingibst.

Was bedeutet es, wenn zwei Zahlen teilerfremd sind?

Zwei Zahlen sind teilerfremd, wenn ihr größter gemeinsamer Teiler (ggT) gleich 1 ist, sie also außer der 1 keinen gemeinsamen Faktor besitzen. Zum Beispiel sind 8 und 15 teilerfremd, weil 8 = 2³ und 15 = 3 × 5 keine gemeinsame Primzahl in ihrer Zerlegung haben. Der Rechner prüft das im Modus „Teilerfremd?“ direkt über die Primfaktoren beider Zahlen.

Wozu braucht man das Sieb des Eratosthenes?

Das Sieb des Eratosthenes listet effizient alle Primzahlen bis zu einer bestimmten Obergrenze auf, indem es schrittweise die Vielfachen jeder gefundenen Primzahl aus einer Zahlenliste streicht. Es eignet sich gut, um zum Beispiel alle Primzahlen zwischen 1 und 1.000 auf einen Blick zu sehen, statt jede Zahl einzeln von Hand zu testen.

Primfaktorzerlegung einfach erklärt: Ist meine Zahl eine Primzahl?

Ob für Hausaufgaben, ein Programmierprojekt oder einfach aus Neugier: Diese Anleitung zeigt Schritt für Schritt, wie man eine Zahl in ihre Primfaktoren zerlegt, wie man schnell prüft, ob sie überhaupt eine Primzahl ist, und wie das mit Teilern, ggT und teilerfremden Zahlen zusammenhängt.

Was Primfaktorzerlegung eigentlich bedeutet

KurzantwortPrimfaktorzerlegung heißt, eine Zahl als Produkt von Primzahlen zu schreiben — zum Beispiel 360 = 2³ × 3² × 5. Jede natürliche Zahl größer als 1 lässt sich auf genau eine solche Weise zerlegen.

Eine Primzahl ist eine natürliche Zahl größer als 1, die nur durch 1 und sich selbst teilbar ist — 2, 3, 5, 7, 11, 13 und so weiter. Alle anderen Zahlen größer als 1 heißen zusammengesetzt, weil sie sich als Produkt kleinerer Zahlen schreiben lassen. Genau diese Zerlegung in ihre kleinsten, nicht weiter teilbaren Bausteine nennt man Primfaktorzerlegung.

Nach dem Fundamentalsatz der Arithmetik ist diese Zerlegung für jede Zahl eindeutig, abgesehen von der Reihenfolge der Faktoren. Es gibt also nur eine richtige Antwort — kein Rechenweg führt zu einer anderen gültigen Zerlegung.

Die Methode Schritt für Schritt

KurzantwortMan teilt die Zahl wiederholt durch die kleinste mögliche Primzahl (beginnend bei 2), zählt jeden erfolgreichen Teilungsschritt als Exponent und wechselt zur nächsten Primzahl, sobald keine glatte Teilung mehr möglich ist.

Nehmen wir als Beispiel die Zahl 360. Zuerst wird durch 2 geteilt, so lange es glatt aufgeht: 360 ÷ 2 = 180, 180 ÷ 2 = 90, 90 ÷ 2 = 45 — jetzt geht 2 nicht mehr glatt auf, also war der Exponent von 2 gleich 3. Weiter geht es mit der nächsten Primzahl, 3: 45 ÷ 3 = 15, 15 ÷ 3 = 5 — Exponent von 3 ist 2. Übrig bleibt 5, was selbst eine Primzahl ist. Das Ergebnis:

Beispiel: Primfaktorzerlegung von 360
Schritt	Division	Ergebnis
1	360 ÷ 2	180
2	180 ÷ 2	90
3	90 ÷ 2	45
4	45 ÷ 3	15
5	15 ÷ 3	5
Ergebnis		2³ × 3² × 5

Bei sehr großen Zahlen (viele Stellen) wird diese Methode von Hand unpraktisch langsam. Der ToolPico-Rechner löst das, indem er bei kleinen Zahlen dieselbe Probedivision anwendet, aber bei großen Zahlen automatisch auf einen schnellen, Miller-Rabin-basierten Primzahltest und den Pollard-Rho-Algorithmus zur Faktorisierung umschaltet — beides läuft direkt im Browser, ohne dass Daten irgendwohin gesendet werden.

Teiler, ggT und teilerfremde Zahlen

KurzantwortSobald die Primfaktorzerlegung bekannt ist, lassen sich daraus direkt alle Teiler einer Zahl, ihr größter gemeinsamer Teiler (ggT) mit einer zweiten Zahl und die Frage, ob beide teilerfremd sind, ableiten.

Die Teiler einer Zahl ergeben sich aus allen Kombinationen ihrer Primfaktoren mit den jeweiligen Exponenten. Für 12 = 2² × 3 sind das 1, 2, 3, 4, 6 und 12 — sechs Teiler insgesamt. Zwei Zahlen sind teilerfremd, wenn ihre Primfaktorzerlegungen keine gemeinsame Primzahl enthalten, ihr ggT also 1 ist. Ein Beispiel: 8 = 2³ und 15 = 3 × 5 haben keine gemeinsame Primzahl, sind also teilerfremd — obwohl beide Zahlen selbst zusammengesetzt sind.

ggT und kgV: Der größte gemeinsame Teiler (ggT) ist das Produkt der Primfaktoren, die beide Zahlen gemeinsam haben (jeweils mit dem kleineren Exponenten); das kleinste gemeinsame Vielfache (kgV) nimmt dagegen jeden vorkommenden Primfaktor mit dem größeren Exponenten. Für 12 und 18 (2²×3 und 2×3²) ergibt sich ggT = 2×3 = 6 und kgV = 2²×3² = 36.

Primzahlen in einem Bereich finden

KurzantwortUm alle Primzahlen zwischen zwei Grenzen aufzulisten, verwendet man am effizientesten das Sieb des Eratosthenes, das systematisch die Vielfachen jeder gefundenen Primzahl aus einer Liste streicht.

Statt jede einzelne Zahl eines Bereichs per Probedivision zu testen, streicht das Sieb des Eratosthenes ab 2 beginnend alle Vielfachen jeder neu gefundenen Primzahl. Was am Ende unmarkiert bleibt, sind die Primzahlen. Zwischen 1 und 100 gibt es so beispielsweise 25 Primzahlen (2 bis 97), zwischen 1 und 1.000 sind es 168 — praktisch, wenn man etwa für ein Sudoku-Rätsel, eine Verschlüsselungsübung oder schlicht aus Interesse schnell eine Übersicht braucht. (Als Beispielrechnung: Wer für ein Schulprojekt „alle Primzahlen bis 500” braucht, bekommt mit dem Sieb sofort eine vollständige, geprüfte Liste statt manuell abzuzählen.)

Primfaktorzerlegung einfach erklärt: Ist meine Zahl eine Primzahl?

Was Primfaktorzerlegung eigentlich bedeutet

Die Methode Schritt für Schritt

Teiler, ggT und teilerfremde Zahlen

Primzahlen in einem Bereich finden

Häufig gestellte Fragen

Verwandte Ratgeber