Primfaktorzerlegung Rechner

Was ist Primfaktorzerlegung Rechner?

Formel

Berechnung

1. Geben Sie eine positive ganze Zahl von 2 bis 10.000.000 ein.
2. Der Algorithmus beginnt mit der Division durch 2, der kleinsten Primzahl.
3. Jedes Mal, wenn die Zahl ohne Rest teilbar ist, wird der Teiler als Faktor notiert.
4. Wenn 2 nicht mehr ohne Rest teilt, versucht der Algorithmus 3, 5, 7, 11, ...
5. Dies wird fortgesetzt, bis die verbleibende Zahl 1 ist oder selbst eine Primzahl ist.
6. Die Faktorisierung wird in Exponentialform geschrieben: n = p₁^a₁ × p₂^a₂ × ...
7. Die Teiler werden mit der Formel τ(n) = (a₁+1)(a₂+1)···(aₖ+1) gezählt.

Beispiel

Wichtige Begriffe erklärt

Primzahl

Eine ganze Zahl > 1, die nur durch 1 und sich selbst teilbar ist

Zusammengesetzte Zahl

Eine ganze Zahl > 1, die keine Primzahl ist

Fundamentalsatz der Arithmetik

Jede ganze Zahl > 1 hat eine eindeutige Primfaktorzerlegung

Probedivision

Faktorisierungsalgorithmus, der Teilbarkeit durch aufeinanderfolgende Primzahlen testet

Exponent

In p^a gibt der Exponent a an, wie oft der Primfaktor p vorkommt

Teilerfunktion τ(n)

Zählt die Anzahl der positiven Teiler von n

Häufige Anwendungsfälle

• Kürzen von Brüchen auf den kleinsten gemeinsamen Nenner
• Bestimmen von ggT und kgV von Zahlen
• RSA-Verschlüsselung und Public-Key-Kryptografie
• Lösen zahlentheoretischer Probleme in Mathematikwettbewerben
• Teilbarkeitsregeln in der Mathematik verstehen
• Algebraisches Faktorisieren und Polynomvereinfachung