Primfaktorzerlegung
Eine ganze Zahl in ihre Primfaktoren zerlegen, ihre Teiler auflisten und prüfen, ob sie prim ist.
Läuft vollständig in Ihrem Browser. Nichts wird hochgeladen, protokolliert oder gespeichert.
Primfaktorzerlegung
2^3 × 3^2 × 5
- Ist sie prim?
- nein
- Verschiedene Primfaktoren
- 3
- Wie viele Teiler
- 24
- Teiler
- 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360
Jede ganze Zahl über 1 ist ein Produkt von Primzahlen, und es gibt für sie nur ein solches Produkt — das ist der Fundamentalsatz der Arithmetik. Dies findet es und alles, was daraus folgt: wie viele Teiler die Zahl hat und welche.
Wie es funktioniert
Probedivision, mit einer Abkürzung: Sind 2 und 3 herausgenommen, liegt jede verbleibende Primzahl einen Schritt neben einem Vielfachen von sechs, die Kandidaten schreiten also in Sechserschritten statt in Zweierschritten. Was das Sieb überlebt, ist selbst prim und geht als letzter Faktor ein.
Die Teiler werden aus der Zerlegung gebaut und nicht dadurch, dass jede Zahl bis n geprüft wird. Eine als 2³ × 3² × 5 geschriebene Zahl hat (3+1) × (2+1) × (1+1) = 24 Teiler, und jeder ist eine Wahl, wie viele von jeder Primzahl genommen werden — sie aufzulisten kostet also nichts mehr, sobald die Zerlegung bekannt ist.
Die Obergrenze ist eine Billion. Die Probedivision berührt höchstens die Quadratwurzel der Zahl, und das sind dort eine Million Schritte — schnell. Darüber ließe eine Zahl, die zufällig das Produkt zweier großer Primzahlen ist, die Seite eine Minute lang laden, daher lehnt sie stattdessen ab.
Beispiele
| Fall | Eingabe | Ergebnis |
|---|---|---|
| Eine Zahl mit vielen Teilern | 360 | 2³ × 3² × 5 — 24 Teiler |
| Eine Primzahl | 97 | 97 — prim, 2 Teiler |
| Eine Zweierpotenz | 1024 | 2¹⁰ — 11 Teiler |
Häufige Fragen
Warum beginnt es bei 2 und nicht bei 1?
Weil 1 keine Primfaktorzerlegung hat und sie prim zu nennen die Eindeutigkeit zerbräche, auf der das ganze Gebiet ruht: Wäre 1 prim, dann wäre 6 gleich 2 × 3 und 1 × 2 × 3 und 1 × 1 × 2 × 3, und es gäbe keine einzige Antwort mehr. Null ist noch schlimmer — jede Zahl teilt sie.
Wie viele Teiler hat eine Zahl?
Addieren Sie eins zu jedem Exponenten der Zerlegung und multiplizieren Sie. 360 ist 2³ × 3² × 5, also 4 × 3 × 2 = 24. Eine Primzahl hat 2 — sich selbst und 1 —, und eine Quadratzahl hat immer eine ungerade Anzahl, weil ein Teiler sein eigener Partner ist.
Warum gibt es eine Obergrenze?
Die Probedivision ist exakt und schnell, bis sie es nicht mehr ist. Der schlimmste Fall ist ein Produkt zweier Primzahlen nahe der Quadratwurzel, und die Grenze hier liegt dort, wo dieser Fall noch innerhalb eines Seitenaufrufs zurückkommt. Eine Ablehnung sagt Ihnen, was passiert ist; eine Zeitüberschreitung sagt Ihnen nichts.
Werden so Verschlüsselungsschlüssel gebrochen?
Nein, und das ist eher der Punkt. RSA ruht auf der Schwierigkeit, eine Zahl von einigen hundert Stellen zu faktorisieren; Probedivision auf einer davon überdauerte das Universum. Die Verfahren, die es besser können, gibt es, und sie reichen immer noch nicht annähernd, und deshalb funktioniert das Verfahren.
Gut zu wissen
- Teiler werden bis zu vierundsechzig Stück vollständig aufgeführt; darüber erscheint nur die Anzahl, denn eine Seite mit neunhundert Zahlen liest niemand.