Rechner für die Primfaktorzerlegung
Eine Zahl als Produkt von Primzahlen schreiben und sofort sehen, ob sie selbst prim ist.
Primfaktorzerlegung
Primfaktorzerlegung: 2³ × 3² × 5
- Ausgeschrieben
- 2 × 2 × 2 × 3 × 3 × 5
- Anzahl der Teiler
- 24
- Nächste Primzahl
- 367
- Vorherige Primzahl
- 359
Diese Zahl ist zusammengesetzt: Sie hat Teiler außer 1 und sich selbst.
| Primzahl | Potenz | Wert |
|---|---|---|
| 2 | 3 | 8 |
| 3 | 2 | 9 |
| 5 | 1 | 5 |
So funktioniert es
Jede ganze Zahl über 1 ist bis auf die Reihenfolge auf genau eine Weise ein Produkt von Primzahlen. Der Rechner teilt zuerst die kleinen Primzahlen ab und verwendet dann die Pollard-Rho-Methode, um größere Faktoren zu zerlegen.
Jeder Faktor wird mit einem deterministischen Miller-Rabin-Test als prim bestätigt, der für Zahlen dieser Größe nachweislich korrekt ist. Die Anzahl der Teiler ergibt sich aus den Exponenten: Jeder wird um 1 erhöht, und die Ergebnisse werden multipliziert.
Formel
n = p₁^a₁ × p₂^a₂ × … × pₖ^aₖ Teiler = (a₁ + 1)(a₂ + 1)…(aₖ + 1)
Rechenbeispiel
360 = 2 × 2 × 2 × 3 × 3 × 5 = 2³ × 3² × 5. Sie hat (3 + 1)(2 + 1)(1 + 1) = 24 Teiler. Die nächsten Primzahlen sind 359 und 367.
Häufige Fragen
Ist 1 eine Primzahl?
Nein. Eine Primzahl hat genau zwei Teiler, 1 und sich selbst; 1 hat nur einen. Ohne die 1 bleibt die Primfaktorzerlegung eindeutig.
Ist 2 die einzige gerade Primzahl?
Ja. Jede andere gerade Zahl ist durch 2 teilbar und hat daher mindestens drei Teiler.
Wie prüft man, ob eine große Zahl prim ist?
Probedivision ist für große Zahlen zu langsam, daher verwendet man Tests wie Miller-Rabin. Mit den passenden Testbasen liefert er für Zahlen dieser Größe eine sichere Antwort.