Primfaktorzerlegung-Rechner

360 = 2^3 * 3^2 * 5; Omega(360) = 3 + 2 + 1 = 6; d(360) = (3+1) * (2+1) * (1+1) = 24

n

Die Zahl, die zerlegt wird — eine ganze Zahl von 1 bis 1.000.000. Der Bereich ist der, den das Zahlentheorie-Modul durchgehend verwendet, er stimmt also genau mit der Teiler-Seite überein, und wer zwischen beiden wechselt, findet dieselben Grenzen. Nachkommastellen werden abgelehnt statt gerundet, und 0 sowie negative Zahlen werden abgelehnt, weil die Primfaktorzerlegung eine Aussage über positive ganze Zahlen ist

p

Ein Primfaktor, also eine Primzahl, die n genau teilt. Die Seite findet sie durch Probedivision in aufsteigender Reihenfolge, die kleinste Primzahl wird also immer zuerst herausgezogen und die gedruckte Zerlegung läuft stets von der kleinsten Primzahl zur größten. Für 360 sind das die Primzahlen 2, 3 und 5, und keine andere Primzahl teilt sie

e

Der Exponent zu einer Primzahl, also wie oft diese Primzahl im Produkt vorkommt. 360 ist 2 × 2 × 2 × 3 × 3 × 5, die 2 kommt also dreimal vor und die 3 zweimal. Eine Primzahl, die nur einmal vorkommt, wird ganz ohne Exponenten gedruckt: Die 5 in 360 steht als schlichte 5 und nicht als 5^1, was die übliche Konvention ist und kurze Zerlegungen lesbar hält

2^3 * 3^2 * 5

Die Zerlegung von 360, so wie sie gedruckt wird, und zugleich die voreingestellte Eingabe. Das Dachzeichen steht für den Exponenten und der Stern für die Multiplikation, das Ganze übersteht also das Kopieren in ein reines Textfeld oder ein Suchfeld. Für jede ganze Zahl über 1 gibt es genau einen solchen Ausdruck, und das macht es lohnend, ihn zu drucken: 360 lässt sich nicht auch als irgendein anderes Produkt von Primzahlen schreiben

Omega(360) = 3 + 2 + 1 = 6

Die Anzahl der Primfaktoren mit Wiederholungen: drei Zweien, zwei Dreien und eine Fünf machen sechs. Diese Anzahl überrascht, weil sich 360 so anfühlt, als wäre sie aus drei Primzahlen gebaut und nicht aus sechs. Das Rezept ist, die Exponenten zu addieren statt die verschiedenen Primzahlen zu zählen, und die beiden Antworten gehen immer dann auseinander, wenn ein Exponent über 1 liegt

d(360) = (3+1) * (2+1) * (1+1) = 24

Die Anzahl der positiven Teiler, aus denselben Exponenten ausgerechnet, indem man zu jedem eins addiert und dann multipliziert. Die Liste lautet 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180 und 360 — vierundzwanzig Stück. Das ist eine andere Frage als die darüber: Sie zählt die Zahlen, die 360 teilen, und nicht die Primzahlen, aus denen 360 gebaut ist

Die Zerlegung ist das, was man braucht, wenn eine Frage auf die multiplikative Struktur einer Zahl zielt und nicht auf ihre Größe. Einen Bruch oder eine Wurzel zu vereinfachen ist der Alltagsfall: Die Wurzel aus 72 wird zu 6√2, weil 72 = 2³ × 3² ist, und der Exponent jeder Primzahl sagt, wie viel davon unter dem Wurzelzeichen hervorkommen kann — das ist dieselbe Zerlegung, die die Wurzel-Seite liest. Den größten gemeinsamen Teiler oder das kleinste gemeinsame Vielfache zweier Zahlen zu finden ist ebenfalls das, einmal pro Zahl gerechnet: die gemeinsamen Primzahlen mit ihren kleineren Exponenten ergeben das erste, alle Primzahlen mit ihren größeren Exponenten das zweite. Teilbarkeitsfragen beantwortet man genauso, denn eine Zahl teilt eine andere genau dann ohne Rest, wenn deren Primzahlen und Exponenten alle in der anderen vorhanden sind. In der Zahlentheorie entscheidet die Zerlegung, ob eine Zahl prim oder eine zusammengesetzte Zahl ist, wie viele Teiler sie hat, ob sie ein Quadrat ist (alle Exponenten gerade) und ob sie ein Kubus ist. Auch die Grenzen des Verfahrens sollte man kennen: Die Probedivision ist bei einer Million schnell und bei einer hundertstelligen Zahl hoffnungslos, und genau diese Lücke zwischen leicht und schwer ist es, auf der die Public-Key-Kryptografie aufbaut. Wenn die Frage lautet, welche Zahlen Ihre Zahl teilen, und nicht, welche Primzahlen sie aufbauen, listet die Teiler-Seite sie auf; wenn sie lautet, ob die Zahl überhaupt prim ist, beantwortet die Primzahl-Seite das direkt.

1. Der Standardfall: 360

   1. 360 ist gerade, also durch 2 teilen: 360 / 2 = 180, dann 180 / 2 = 90, dann 90 / 2 = 45 — dreimal insgesamt
   2. 45 ist nicht gerade; die nächste Primzahl ist 3, und 45 / 3 = 15, dann 15 / 3 = 5 — zweimal
   3. 5 ist prim, die Zerlegung ist also 2 × 2 × 2 × 3 × 3 × 5, geschrieben 2^3 * 3^2 * 5
   4. Die Primfaktoren mit Wiederholungen zählen: 3 + 2 + 1 = 6
   5. Die Teiler aus den Exponenten zählen: (3 + 1) × (2 + 1) × (1 + 1) = 4 × 3 × 2 = 24

   Die voreingestellte Eingabe und die, die zeigt, warum überhaupt zwei Anzahlen gedruckt werden. Sechs und vierundzwanzig stehen nebeneinander, und wer erwartet, dass sie übereinstimmen, hält eine davon für kaputt. Sie sind es nicht: Sechs ist die Anzahl der Primzahlstücke, aus denen die Zahl besteht, wenn man jede Wiederholung mitzählt, und vierundzwanzig ist die Anzahl der Zahlen, die sie teilen. Der Abstand zwischen ihnen kommt von den Exponenten — jede Wiederholung einer Primzahl multipliziert die Teileranzahl, ohne zur Stückzahl viel beizutragen. Prüfen Sie eine der beiden von Hand, und die Rechnung ist kurz; prüfen Sie beide, und Sie behalten, welche welche ist.

2. Der kleine Fall, der den Abstand zeigt: 12

   1. 12 / 2 = 6, und 6 / 2 = 3, die 2 kommt also zweimal vor
   2. 3 ist prim, die Zerlegung ist also 2^2 * 3
   3. Die Primfaktoren mit Wiederholungen zählen: 2 + 1 = 3, das sind 2, 2 und 3
   4. Die Teiler auflisten: 1, 2, 3, 4, 6, 12 — sechs Stück
   5. Mit dem Rezept nachprüfen: (2 + 1) × (1 + 1) = 3 × 2 = 6, was zur Liste passt

   Das klarste kleine Beispiel für die Verwechslung, um die diese Seite herum gebaut ist, weil beide Anzahlen klein genug sind, um sie in Sekunden von Hand nachzuprüfen. Zwölf besteht aus drei Primzahlen — 2, 2 und 3 —, und sechs Zahlen teilen sie. Die Ausgabe als »3 Teiler« oder als »6 Primfaktoren« zu lesen klingt beides plausibel und ist beides falsch. Die Teilerliste zeigt außerdem die Paarung, die sechs zu einer geraden Anzahl macht: 1 mit 12, 2 mit 6, 3 mit 4. Zwölf ist kein Quadrat, kein Teiler paart sich also mit sich selbst, und deshalb ist die Anzahl gerade.

3. Der sperrige Fall: 1

   1. 1 ist durch keine Primzahl teilbar — die Division durch 2, 3, 5 oder eine andere lässt einen Bruch übrig
   2. Es gibt also keine Primfaktoren, und ihre Anzahl ist 0
   3. Die einzige positive Zahl, die 1 teilt, ist 1 selbst, die Teileranzahl ist also 1
   4. Die Zerlegung wird als einzelne Ziffer 1 gedruckt und nicht als leeres Feld

   Der Fall, der entschieden werden muss statt hergeleitet zu werden, und die Entscheidung lautet, 1 zu drucken. Die Zerlegung leer zu lassen würde wie ein gescheiterter Rechenlauf aussehen, und das ist das Einzige, wonach eine Ergebnisanzeige nie aussehen darf. Die beiden Anzahlen fallen dann ehrlich aus: gar keine Primzahlen und ein Teiler. Eins ist weder prim noch zusammengesetzt — sie ist das neutrale Element der Multiplikation, die Zahl, die nichts ändert, wenn man mit ihr multipliziert —, und die Seite tut nicht so, als wäre es anders. Sie wird angenommen statt abgelehnt, weil der Eingabebereich bei 1 beginnt, und einen Bereich zu erklären, der seinen eigenen untersten Wert ausschließt, wäre die seltsamere Sache.

Die Eingabe muss eine ganze Zahl von 1 bis 1.000.000 sein. Null wird abgelehnt: Jede Primzahl teilt null, das Produkt müsste also unendlich sein. Negative Zahlen werden aus einem verwandten Grund abgelehnt — die Primzahlen teilen sie zwar weiterhin, aber das Vorzeichen muss getrennt mitgeführt werden, und die Aussage der eindeutigen Zerlegung gilt für positive Zahlen. Nachkommastellen werden abgelehnt statt gerundet, denn das Runden würde stillschweigend eine Frage über eine andere Zahl beantworten. Die Obergrenze von einer Million stammt aus dem gemeinsamen Zahlentheorie-Modul und ist eine Frage des Aufwands und nicht der Richtigkeit: Die Probedivision durch jede Primzahl bis zur Wurzel ist bei einer Million schnell und bei einer Zahl mit zwanzig Stellen hoffnungslos. Das ist eine echte Grenze des Verfahrens, und es ist dieselbe Grenze, die die Public-Key-Kryptografie funktionieren lässt. Die Seite berichtet die Zerlegung und zwei Anzahlen und sonst nichts: Sie listet die Teiler nicht selbst auf, berechnet keinen größten gemeinsamen Teiler und kein kleinstes gemeinsames Vielfaches über mehrere Zahlen hinweg und vereinfacht keine Wurzeln und keine Brüche. Ein Exponent von 1 wird nie gedruckt, eine Primzahl, die einmal vorkommt, erscheint also als nackte Zahl, und das Multiplikationszeichen ist durchgehend ein Stern, die Ausgabe ist also reiner ASCII-Text ohne Tausenderpunkte. Die Referenztabelle unten zeigt schließlich vier feste Zahlen und folgt nicht Ihrer Eingabe.

Was ist der Unterschied zwischen den beiden Anzahlen auf dieser Seite?

Die erste zählt die Primfaktoren mit Wiederholungen, die zweite zählt die Teiler. Für 12 lauten die Antworten 3 und 6, und beide sind richtig. Zwölf ist 2 × 2 × 3, besteht also aus drei Primzahlstücken; und 1, 2, 3, 4, 6 und 12 teilen sie alle, sie hat also sechs Teiler. Die Verwechslung ist natürlich, weil die beiden Zahlen bei kleinen Eingaben dicht beieinanderliegen. Das Rezept für die erste ist, die Exponenten zu addieren; das Rezept für die zweite ist, zu jedem Exponenten eins zu addieren und dann zu multiplizieren. Diese Multiplikation ist der Grund, warum die zweite Anzahl so viel schneller davonläuft — jede zusätzliche Wiederholung einer Primzahl multipliziert die Teileranzahl, während sie die erste nur um eins erhöht.

Gibt es für eine Zahl nur eine einzige Primfaktorzerlegung?

Ja, und das ist ein Satz und keine Konvention. Jede ganze Zahl über 1 lässt sich als Produkt von Primzahlen schreiben, und es gibt genau eine Art, das zu tun, sobald man die Reihenfolge außer Acht lässt. Dreihundertsechzig ist immer nur 2³ × 3² × 5; es ist nicht auch irgendein anderes Produkt von Primzahlen. Das Ergebnis heißt Fundamentalsatz der Arithmetik, und ohne ihn wäre das Drucken einer Zerlegung eine Kuriosität statt einer Antwort. Er ist auch der Grund, warum die Seite die kleinste Primzahl zuerst drucken kann und sicher sein darf, dass das die kanonische Form ist — die Reihenfolge ist der Lesbarkeit wegen gewählt, und es geht nichts verloren, wenn man sie festlegt.

Was macht die Seite mit der 1?

Sie druckt 1 als Zerlegung, mit null Primfaktoren und einem Teiler. Eins ist weder prim noch zusammengesetzt: Sie hat im üblichen Sinn keine Primfaktorzerlegung, und der Satz oben ist genau deshalb für Zahlen über 1 formuliert. Eine leere Ergebnisanzeige würde aber wie ein gescheiterter Rechenlauf aussehen, also druckt die Seite die Ziffer und berichtet die beiden Anzahlen ehrlich. Die Teileranzahl von 1 ist tatsächlich 1, denn die einzige positive Zahl, die 1 teilt, ist 1 selbst, und die Anzahl der Primfaktoren ist tatsächlich 0. Eins wird angenommen statt abgelehnt, weil der Eingabebereich bei 1 beginnt, und den untersten Wert des eigenen Bereichs abzulehnen kostet mehr Erklärung, als ihn zu beantworten.

Warum hört es bei einer Million auf?

Weil die Probedivision das Verfahren ist und ihr Aufwand mit der Wurzel der Zahl wächst. Die Primzahlen einer Zahl nahe einer Million zu finden heißt, Teiler bis Tausend zu prüfen, was augenblicklich geht. Die Primzahlen einer Zahl mit zwanzig Stellen zu finden heißt, bis zu zehn Milliarden zu prüfen, und das geht nicht. Diese Lücke ist kein Implementierungsdetail — sie ist eine echte Eigenschaft des Problems, und sie ist die Annahme, auf der die Public-Key-Kryptografie aufbaut, wo die Schwierigkeit, große Zahlen zu zerlegen, eine Nachricht geheim hält. Innerhalb einer Million kommt jede Antwort sofort zurück, und die Obergrenze steht in der Eingabe statt in einem Timeout versteckt.

Wann will man eine Zerlegung statt einer Teilerliste?

Wenn die Frage auf die Struktur zielt und nicht auf die Zugehörigkeit. Die Wurzel aus 72 zu vereinfachen braucht 72 = 2³ × 3², weil die Exponenten sagen, wie viel von jeder Primzahl unter dem Wurzelzeichen hervorkommen kann, was 6√2 ergibt. Den größten gemeinsamen Teiler zweier Zahlen zu finden braucht beide Zerlegungen, denn die Antwort sind die gemeinsamen Primzahlen mit ihren kleineren Exponenten. Ob eine Zahl ein Quadrat ist, sieht man an den Exponenten — alle gerade heißt ja. Die Teiler aufzulisten ist eine andere Frage, und je nach Zahl kann die Antwort sehr viel länger sein: 720.720 hat 240 davon, das ist viel zum Drucken und wenig zum Anschauen. Die Teiler-Seite dieser Website listet sie auf, wenn das gebraucht wird.

Warum wird kein Exponent gedruckt, wenn eine Primzahl nur einmal vorkommt?

Weil 5^1 für eine einzelne 5 nur Ballast ist. Die Konvention in der Mathematik ist, einen Exponenten nur zu drucken, wenn er größer als eins ist, 360 ist also 2^3 * 3^2 * 5 mit einem nackten letzten Term. Es geht nichts verloren, wenn man ihn weglässt: Das Fehlen eines Exponenten bedeutet eindeutig, dass der Exponent eins ist, und eine Zerlegung, die nur aus einfachen Primzahlen besteht — was eine quadratfreie Zahl ausmacht —, liest sich als schlichtes Produkt ganz ohne Dachzeichen. Dieselbe Konvention ist der Grund, warum 97, das prim ist, einfach als 97 gedruckt wird und nicht als 97^1.

• Prime Factorization — from Wolfram MathWorld (English original; das Schreiben einer ganzen Zahl als Produkt von Primzahlen und die Verfahren, die diese Primzahlen finden) — Wolfram MathWorld (United States)
• Prime Factor — from Wolfram MathWorld (English original; was ein einzelner Primfaktor ist und wie er sich zu den übrigen Faktoren der Zahl verhält) — Wolfram MathWorld (United States)
• Divisor Function — from Wolfram MathWorld (English original; die Anzahl der positiven Teiler, die Formel, die sie aus den Exponenten bildet, und ihr Verhalten bei Potenzen einer einzelnen Primzahl) — Wolfram MathWorld (United States)
• Primfaktorzerlegung — Mathebibel: die deutschsprachige Darstellung des Zerlegens in Primfaktoren, mit der Schreibweise, die im deutschen Unterricht üblich ist, und den Teilbarkeitsregeln, die dabei helfen — Mathebibel (Deutschland)