Primfaktorzerlegung-Rechner

Dieser Primfaktorzerlegung-Rechner zerlegt jede natürliche Zahl von 2 bis 999.999.999 in ihre Primfaktoren und zeigt das Ergebnis in Exponentenform, eine Schritt-für-Schritt-Divisionstabelle und die vollständige Liste aller Teiler. Er sagt Ihnen außerdem, ob die Zahl selbst eine Primzahl ist, und da er die Primfaktoren beliebiger zwei Zahlen auflistet, dient er zugleich als schneller Test auf Teilerfremdheit. Unten finden Sie klare Antworten auf die Fragen, was eine Primzahl ist, was ein Primfaktor ist, was teilerfremd bedeutet, sowie eine praktische Primzahltabelle.

Was ist eine Primzahl?

Eine Primzahl ist eine natürliche Zahl größer als 1, die außer 1 und sich selbst keine positiven Teiler hat. Primzahlen sind die Bausteine jeder anderen ganzen Zahl, weshalb sie so zentral für die Mathematik sind. Die kleinste Primzahl ist 2 — zugleich die einzige gerade — und die ersten 20 lauten 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 und 71. Die Zahl 1 ist keine Primzahl, denn eine solche muss genau zwei verschiedene Teiler haben (1 und sich selbst).

Gibt es eine größte Primzahl? Nein — Euklid bewies um 300 v. Chr., dass es unendlich viele gibt, sie gehen also nie aus. Die größte bekannte ist heute eine 41 Millionen Stellen lange Mersenne-Primzahl, M136279841, entdeckt 2024. Es wird immer eine noch größere geben, die darauf wartet, gefunden zu werden.

Primzahltabelle (Primzahlen bis 100)

Die Primzahltabelle unten listet jede Primzahl bis 100 mit der Anzahl pro Bereich auf — eine schnelle Referenz für Hausaufgaben und Teilbarkeitsprüfungen.

Primzahlen und zusammengesetzte Zahlen

Jede natürliche Zahl größer als 1 ist entweder prim oder zusammengesetzt. Eine Primzahl hat genau zwei Teiler, eine zusammengesetzte mehr als zwei — das heißt, sie lässt sich in kleinere Primfaktoren zerlegen. Zum Beispiel ist 12 zusammengesetzt (12 = 2² × 3), aber 13 ist prim. Die Zahl 1 gehört zu keiner der beiden Gruppen: Sie hat nur einen Teiler. Manche dieser Zahlen treten paarweise im Abstand von 2 auf, etwa (11, 13) oder (17, 19); diese heißen Primzahlzwillinge und gehören zu den berühmten ungelösten Problemen der Zahlentheorie.

Was ist ein Primfaktor?

Primfaktoren sind die Primzahlen, die eine Zahl ohne Rest teilen. Nach dem Fundamentalsatz der Arithmetik lässt sich jede ganze Zahl größer als 1 auf genau eine Weise als Produkt von Primzahlen schreiben — ihre eindeutige Primfaktorzerlegung. Einige durchgerechnete Beispiele:

• 360 = 2³ × 3² × 5
• 72 = 2³ × 3²
• 1001 = 7 × 11 × 13
• 100 = 2² × 5²

Wie führt man eine Primfaktorzerlegung durch?

1. Beginnen Sie mit der Division durch die kleinste Primzahl, 2.
2. Wenn 2 nicht mehr glatt teilt, gehen Sie zur nächsten Primzahl (3, 5, 7...).
3. Fahren Sie fort, bis der Quotient 1 ist.
4. Schreiben Sie wiederholte Faktoren in Exponentenform.

Beispiel: 72 ÷ 2 = 36, 36 ÷ 2 = 18, 18 ÷ 2 = 9, 9 ÷ 3 = 3, 3 ÷ 3 = 1 → 72 = 2³ × 3². Der Rechner oben führt genau diese Schritte aus und zeigt sie in der Divisionstabelle, sodass Sie den Rechenweg nachvollziehen können.

Was bedeutet teilerfremd?

Zwei Zahlen sind teilerfremd (auch relativ prim genannt), wenn ihr größter gemeinsamer Teiler 1 ist — sie teilen keinen gemeinsamen Faktor außer 1. „Was bedeutet teilerfremd" läuft also darauf hinaus, keinen gemeinsamen Primfaktor zu haben: 8 = 2³ und 9 = 3² sind teilerfremde Zahlen, weil sie keinen Primfaktor gemeinsam haben, obwohl keine von beiden selbst prim ist.

Um dieses Tool als Test auf Teilerfremdheit zu nutzen, zerlegen Sie beide Zahlen und vergleichen ihre Primfaktoren. Teilen die beiden Listen nichts, sind die Zahlen teilerfremd. Zum Beispiel teilen 35 = 5 × 7 und 48 = 2⁴ × 3 keinen Faktor, sie sind also teilerfremd. Teilerfremdheit ist wichtig in der Kryptografie (der RSA-Algorithmus beruht auf teilerfremden Exponenten), beim Kürzen von Brüchen und in der modularen Arithmetik.

Anwendungen der Primfaktorzerlegung

• ggT und kgV: Direkt aus den gemeinsamen und kombinierten Primfaktoren zweier Zahlen ablesbar.
• Brüche kürzen: Gemeinsame Primfaktoren in Zähler und Nenner streichen.
• Kryptografie: Die Sicherheit von RSA beruht auf der Schwierigkeit, sehr große Zahlen zu faktorisieren.
• Zahlentheorie: Grundlage für Teilbarkeitsregeln, vollkommene Zahlen und viele Beweise.

Geben Sie oben eine beliebige Zahl ein, um ihre vollständige Primfaktorzerlegung, die Divisionsschritte und alle Teiler sofort zu sehen. Weitere Antworten finden Sie in den häufig gestellten Fragen unten.

Teilbarkeitsregeln als Abkürzung

Bevor Sie überhaupt dividieren, helfen Teilbarkeitsregeln dabei, mögliche Primfaktoren schnell zu erkennen. Mit ihnen sehen Sie auf einen Blick, durch welche kleine Primzahl sich eine Zahl teilen lässt:

• Durch 2: wenn die letzte Stelle gerade ist (0, 2, 4, 6, 8). Beispiel: 364 ist gerade.
• Durch 3: wenn die Quersumme durch 3 teilbar ist. Beispiel: 261 → 2+6+1 = 9, teilbar durch 3.
• Durch 5: wenn die letzte Stelle 0 oder 5 ist. Beispiel: 1.235.
• Durch 9: wenn die Quersumme durch 9 teilbar ist. Beispiel: 729 → 7+2+9 = 18.
• Durch 11: wenn die alternierende Quersumme durch 11 teilbar ist. Beispiel: 2.728 → (8−2+7−2) = 11.

Diese Regeln ersetzen die Zerlegung nicht, beschleunigen aber den ersten Schritt — besonders bei Kopfrechnen und in Klausuren ohne Taschenrechner.

Das Sieb des Eratosthenes

Wer alle Primzahlen bis zu einer Grenze finden möchte, nutzt das Sieb des Eratosthenes, ein über 2.000 Jahre altes Verfahren. Man schreibt alle Zahlen von 2 bis zur Grenze auf, streicht dann nacheinander alle Vielfachen von 2, von 3, von 5 und so weiter. Was übrig bleibt, sind die gesuchten Zahlen. Um etwa alle bis 30 zu finden, streichen Sie zuerst 4, 6, 8 … (Vielfache von 2), dann 9, 15, 21, 27 (Vielfache von 3) und schließlich 25 (Vielfaches von 5). Übrig bleiben 2, 3, 5, 7, 11, 13, 17, 19, 23 und 29. Das Sieb ist die anschaulichste Methode, um zu verstehen, warum solche Zahlen mit wachsender Größe immer seltener werden, und es bildet die Grundlage vieler moderner Algorithmen zur Suche.