Teiler-Rechner

60 ÷ 1 = 60 ⇒ 1 * 60; 60 ÷ 2 = 30 ⇒ 2 * 30; 60 ÷ 3 = 20 ⇒ 3 * 20; 60 ÷ 4 = 15 ⇒ 4 * 15; 60 ÷ 5 = 12 ⇒ 5 * 12; 60 ÷ 6 = 10 ⇒ 6 * 10; 60 ÷ 7 geht nicht auf, 8 × 8 > 60, Abbruch

n

Die Zahl, die zerlegt wird — eine ganze Zahl von 1 bis 1.000.000. Die 1 ist erlaubt und liefert den einzelnen Teiler 1, eine echte Antwort und kein entarteter Fall: Die 1 teilt jede ganze Zahl und ist damit ihr eigener Teiler

d

Ein Probedivisor, der Reihe nach 1, 2, 3, 4 und so weiter. Die Seite testet nie über die Quadratwurzel von n hinaus, und diese Grenze ist der ganze Trick: Wenn d × e = n gilt und d größer als die Quadratwurzel ist, dann ist e kleiner als sie, also wurde e bereits gefunden und das Paar bereits gedruckt

d * d ≤ n

Die Abbruchregel, ausgeschrieben. Bei der 60 ist der letzte getestete Divisor die 7, denn 7 × 7 = 49 liegt unter 60 und 8 × 8 = 64 darüber. Wegen dieser Regel wächst die Anzahl der Proben mit der Quadratwurzel der Eingabe und nicht mit der Eingabe — eine Million kostet tausend Proben, nicht eine Million

n / d

Der Partner eines Teilers. Wenn d die Zahl n glatt teilt, ist der Quotient die andere Hälfte des Paares, und die Seite erzeugt ihn im selben Schritt. Deshalb kommen die Paare der 60 als 1 * 60, 2 * 30, 3 * 20 und so weiter in der richtigen Reihenfolge heraus, ganz ohne Sortierung: Die kleineren Hälften werden aufsteigend gefunden, also stehen auch die Paare aufsteigend da

1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60

Alle Teiler von 60 als eine flache Liste, aufsteigend. Zwölf Einträge, eine gerade Anzahl — die Paarung geht auf, jeder Teiler hat einen Partner. Die Liste enthält dieselbe Information wie die Faktorpaare, nur anders geordnet: Lesen Sie die Paare und sammeln Sie die Zahlen ein, haben Sie diese Zeile wieder

6 * 6

Das mittlere Paar der 36 und die einzige Form, in der ein Teiler zweimal in einer Zeile steht. Die 36 ist eine Quadratzahl, ihre Teileranzahl ist deshalb ungerade — 1, 2, 3, 4, 6, 9, 12, 18, 36, also neun —, und die Seite druckt das mittlere Paar einmal statt zweimal. Das ist der Grund, warum eine Quadratzahl nie eine gerade Teileranzahl hat

Einen Bruch zu kürzen ist der häufigste Grund, eine Teilerliste zu wollen. Um 42/60 von Hand zu kürzen, suchen Sie eine Zahl, die beide teilt; die Teiler von 60 nennen Ihnen die Kandidaten, und die Teiler von 42 sagen Ihnen, welche davon in Frage kommen — die größte solche Zahl ist der größte gemeinsame Teiler, und der GGT-Rechner beantwortet genau diese Frage, wenn Sie nur sie brauchen. Ein zweiter Nutzen ist das Rechteck mit fester Fläche: Ein Beet von 60 Quadratmetern kann 1 mal 60, 2 mal 30, 3 mal 20, 4 mal 15, 5 mal 12 oder 6 mal 10 sein, und die Faktorpaare sind genau diese Liste möglicher Formen — deshalb werden sie in dieser Form gedruckt. Dieselbe Frage stellt sich, sobald Dinge in gleich große Reihen und Spalten gebracht werden sollen: 60 Gäste an gleich große Tische setzen oder eine Klasse in gleich große Gruppen teilen, ohne dass jemand übrig bleibt. Ein dritter Nutzen ist das Nachprüfen einer Behauptung. Wenn jemand sagt, 91 sei eine Primzahl, entscheidet die Teilerliste das — 1, 7, 13, 91 —, und die Tatsache, dass dort vier Einträge stehen und nicht zwei, ist der Widerlegung genug. Die Teilbarkeitsregeln für 2, 3, 5 und 9 decken die kleinen Fälle von Hand ab, und diese Seite übernimmt dort, wo sie mühsam werden. Wenn die Frage eigentlich auf die Bausteine zielt und nicht auf die Teiler, liegt die Antwort woanders: Der Primfaktorzerlegung-Rechner zerlegt die Zahl in Primzahlen, was diese Seite bewusst nicht tut; der KGV-Rechner und der GGT-Rechner vergleichen zwei Zahlen, statt eine zu beschreiben; und der Brüche-kürzen-Rechner benutzt einen gemeinsamen Teiler, um einen Bruch direkt zu kürzen, ohne Ihnen die Liste zu zeigen.

1. Zwölf Teiler: 60

   1. Probe 1: 60 ÷ 1 = 60 geht auf, also sind 1 und 60 beide Teiler
   2. Probe 2: 60 ÷ 2 = 30, also sind 2 und 30 Teiler; Probe 3: 60 ÷ 3 = 20, das ergibt 3 und 20
   3. Probe 4: 60 ÷ 4 = 15, das ergibt 4 und 15; Probe 5: 60 ÷ 5 = 12, das ergibt 5 und 12
   4. Probe 6: 60 ÷ 6 = 10, das ergibt 6 und 10; Probe 7: 60 ÷ 7 ist keine ganze Zahl
   5. 8 × 8 = 64 liegt über 60, also Abbruch — die zwölf Teiler sind vollständig

   Die Standardeingabe und eine gute Wahl, weil die 60 viele Teiler hat — zwölf, so viele wie keine kleinere Zahl. Beachten Sie, wie billig die Suche war: sieben Probedivisoren statt sechzig. Die Paarzeile und die Teilerliste enthalten dieselben zwölf Zahlen; in den Paaren steht jede nur neben der Zahl, mit der sie multipliziert wird. Ebenso bemerkenswert: Die Paarliste endet mit 6 * 10 und läuft nicht als 10 * 6 weiter — sobald die kleinere Hälfte eines Paares die Quadratwurzel überschreitet, ist jedes weitere Paar die Wiederholung eines schon gedruckten.

2. Eine Quadratzahl: 36

   1. 1 und 36 bilden ein Paar, dann 2 und 18, dann 3 und 12, dann 4 und 9
   2. 6 × 6 = 36, die 6 ist also ihr eigener Partner — die Mitte der Liste
   3. Die 7 teilt die 36 nicht; 7 × 7 = 49 liegt bereits darüber, aber die 6 war der letzte Divisor unterhalb der Quadratwurzel
   4. Die Teiler sind 1, 2, 3, 4, 6, 9, 12, 18, 36 — neun Stück, eine ungerade Anzahl

   Der Fall, der zeigt, warum eine Teileranzahl ungerade sein kann. Jeder Teiler außer der Quadratwurzel hat einen anderen Partner, sie gehen also paarweise auf und tragen eine gerade Anzahl bei; die Quadratwurzel ist mit sich selbst gepaart und trägt eine einzige bei. Das ist der ganze Grund, warum die 36 neun Teiler hat, während die größere 60 auf zwölf kommt und die 12 auf sechs. Die Paarzeile druckt 6 * 6 einmal statt zweimal, und das ist eine Entscheidung: zweimal gedruckt würden die beiden Zeilen sich darüber widersprechen, wie viele Teiler es gibt.

3. Eine Primzahl: 7

   1. Probe 1: 7 ÷ 1 = 7 geht auf, also sind 1 und 7 Teiler
   2. Probe 2: 7 ÷ 2 ist keine ganze Zahl; 3 × 3 = 9 liegt über der 7, also endet die Suche dort
   3. Nichts zwischen 1 und 7 teilt sie
   4. Zwei Teiler und ein Paar — und das ist die Definition einer Primzahl

   Die kürzeste nicht triviale Ausgabe der Seite und die Stelle, an der man sieht, dass eine Primzahl kein gescheiterter Zerlegungsversuch ist. Eine Primzahl ist eine Zahl mit genau zwei Teilern, und diese zwei sind immer die 1 und die Zahl selbst; die Seite berichtet diese Tatsache, statt zu melden, dass sie nichts gefunden hat. Die Abbruchregel leistet hier echte Arbeit — nach der Probe mit der 2 bleibt nichts zu testen, weil 3 × 3 bereits größer als 7 ist. Die Proben mit 3, 4, 5 und 6 würden vier Divisionen kosten und könnten nichts finden.

Die Eingabe muss eine ganze Zahl von 1 bis 1.000.000 sein. Die Null wird abgelehnt: Jede ganze Zahl teilt die Null, ihre Teilerliste wäre also unendlich, und es gäbe nichts Sinnvolles zu drucken. Negative Zahlen werden ebenfalls abgelehnt, obwohl ±1, ±2 und so weiter die −60 alle teilen — die Seite berichtet die positiven Teiler einer positiven Zahl, und eine Teilerliste mit Vorzeichen bräuchte eine Festlegung dazu, ob beide Vorzeichen erscheinen; diese Festlegung trifft die Seite nicht. Dezimalzahlen werden abgelehnt statt gerundet. Die Obergrenze von einer Million hält das Durchprobieren in Grenzen: Die Suche endet bei der Quadratwurzel, der schlimmste Fall sind also tausend Proben, und die Antwortliste kann lang werden, aber nie unübersichtlich. Lang werden kann sie trotzdem — die 720.720 hat 240 Teiler, so viele wie keine andere Zahl unter einer Million —, und eine Liste dieser Größe ist zwar richtig, aber kein Vergnügen zu lesen. Die Seite nennt Teiler und Faktorpaare, nicht Primfaktoren, und der Unterschied ist leicht zu übersehen: Die Teilerliste der 60 enthält 2, 3 und 5, aber die Seite sagt nie, dass 60 = 2² × 3 × 5 ist, und bei einer großen Zahl sind das zwei Fragen mit sehr verschiedenen Kosten. Die Teilbarkeitsregeln für 2, 3, 5 und 9 werden nicht gesondert ausgewiesen — sie gehen einfach im Durchprobieren auf, eine Zahl auf 0 zeigt also 2, 5 und 10 als Teiler, ohne dass die Seite erklärt, warum. Jeder Teiler wird als ganze Zahl in einer durch Kommas getrennten Liste gedruckt, und die Faktorpaare benutzen den Stern als Malzeichen; Tausendertrennzeichen kommen nicht vor. Die Tabelle unten zeigt drei feste Zahlen und folgt nicht Ihrer Eingabe; die Ausgabe darüber ist die, die Ihre Zahl beantwortet.

Was zählt genau als Teiler?

Jede ganze Zahl, die Ihre Zahl ohne Rest teilt. Beide Mitglieder eines Paares zählen, für die 60 läuft die Liste also von der 1 bis hinauf zur 60 — die 1 und die Zahl selbst sind immer Teiler, und die interessanten liegen dazwischen. Brüche zählen nicht, auch wenn sie aufgehen: Die 2,5 passt vierundzwanzigmal in die 60, aber 2,5 ist keine ganze Zahl und damit kein Teiler. Diese Seite listet die positiven Teiler einer positiven Zahl, und das ist die übliche Übereinkunft.

Warum endet die Suche bei der Quadratwurzel?

Weil jenseits davon jeder gefundene Teiler der Partner eines schon gesehenen ist. Wenn d × e = 60 gilt und d größer als die Quadratwurzel von 60 ist, dann ist e kleiner als sie — also wurde e früher getestet und das Paar damals gedruckt. Weiter zu testen kann nur Paare in der anderen Reihenfolge wiederfinden. Deshalb braucht die 60 sieben Probedivisoren statt sechzig, und deshalb wächst der Aufwand dieser Seite mit der Quadratwurzel der Eingabe: Eine Zahl nahe einer Million kostet etwa tausend Proben, nicht eine Million.

Warum hat 36 eine ungerade Anzahl von Teilern?

Weil die 36 eine Quadratzahl ist, ihre Quadratwurzel also mit sich selbst gepaart ist. Jeder andere Teiler hat einen anderen Partner — 1 mit 36, 2 mit 18, 3 mit 12, 4 mit 9 —, und jedes solche Paar trägt zwei zur Anzahl bei. Dann kommt 6 × 6 = 36 und trägt eine bei. Die Summe ist also 4 × 2 + 1 = 9. Allgemein hat eine Zahl genau dann eine ungerade Anzahl von Teilern, wenn sie eine Quadratzahl ist, und das ist der schnellste Weg, einer Teilerliste anzusehen, ob die Zahl eine ist.

Ist das dasselbe wie die Primfaktorzerlegung?

Nein, und der Unterschied ist es wert, klar benannt zu werden. Diese Seite liefert jeden Teiler; die Primfaktorzerlegung zerlegt die Zahl in Primzahlen, die miteinander multipliziert werden. Für die 60 lautet sie 2² × 3 × 5, und die Seite druckt sie nie — wobei 2, 3 und 5 alle in der Teilerliste auftauchen, denn Primzahlen sind Teiler wie jede andere. Der praktische Unterschied ist der Aufwand: Diese Seite arbeitet proportional zur Quadratwurzel der Zahl, während die Primfaktorzerlegung bei großen Zahlen wirklich schwer ist, und genau darauf beruht die Public-Key-Kryptografie.

Kann ich 0 oder eine negative Zahl eingeben?

Nein, und beides ist keine willkürliche Einschränkung. Jede ganze Zahl teilt die Null, ihre Teilerliste würde also nie enden. Bei einer negativen Zahl treten die Teiler in beiden Vorzeichen auf — 1 und −1, 2 und −2 und so weiter —, und diese Seite müsste sich festlegen, ob sie beide listet; das tut sie nicht. Die Eingabe ist eine ganze Zahl von 1 bis 1.000.000. Dezimalzahlen werden ebenfalls abgelehnt statt gerundet, weil das Runden still eine Frage über eine andere Zahl beantworten würde.

Warum sind die Teiler auf zwei Ausgaben verteilt?

Weil sie zwei verschiedene Fragen beantworten. Die flache Liste brauchen Sie, wenn Sie wissen wollen, ob eine bestimmte Zahl Ihre Zahl teilt. Die Faktorpaare brauchen Sie, wenn die Zahl ein Produkt zweier Dinge ist, die Sie wählen — ein Rechteck mit dieser Fläche, gleich große Reihen und Spalten, eine Gruppe, die ohne Rest aufgeht. Ein Beet von 60 Quadratmetern kann 1 mal 60, 2 mal 30, 3 mal 20, 4 mal 15, 5 mal 12 oder 6 mal 10 sein, und diese sechs Formen sind genau die Faktorpaarspalte. Beide Ausgaben enthalten dieselben Zahlen; nur die Anordnung unterscheidet sich.

• Divisor — from Wolfram MathWorld (English original; was es heißt, dass eine ganze Zahl eine andere ohne Rest teilt, und die Übereinkunft, dass jede Zahl sich selbst teilt) — Wolfram MathWorld (United States)
• Prime Number — from Wolfram MathWorld (English original; Zahlen mit genau zwei Teilern und warum diese Definition die Teilerliste sichtbar macht) — Wolfram MathWorld (United States)
• Perfect Square — from Wolfram MathWorld (English original; Zahlen, deren Quadratwurzel ganz ist, und der Grund, warum ihre Teileranzahl immer ungerade ist) — Wolfram MathWorld (United States)
• Teiler — Mathebibel: die deutschsprachige Darstellung der Teiler einer Zahl, der Teilermenge und der Schreibweise, die im deutschen Unterricht üblich ist — Mathebibel (Deutschland)