Primfaktorzerlegungsrechner

Primfaktorzerlegung (Primdekomposition) drückt eine positive ganze Zahl als Produkt von Primzahlen aus. Jede ganze Zahl > 1 hat eine eindeutige Primfaktorzerlegung (Fundamentalsatz der Arithmetik). Beispiel: 360 = 2³ × 3² × 5. Schritte: Finden Sie den kleinsten Primfaktor, dividieren Sie, wiederholen Sie bis der Quotient 1 ist. Algorithmus: Probedivision durch Primzahlen bis √n. Effizient für Zahlen bis etwa 10^12; größere Zahlen erfordern fortgeschrittene Algorithmen (Pollards Rho, Zahlenkörpersieb). Primfaktorzerlegung ist rechnerisch schwierig für sehr große Zahlen – diese Schwierigkeit ist die Grundlage der RSA-Kryptografie.

Kryptografie: RSA und andere Public-Key-Systeme basieren auf der Schwierigkeit, große Zahlen zu faktorisieren. GCD/LCM-Berechnung: GCD(a,b) = Produkt der gemeinsamen Primfaktoren mit minimalen Exponenten. LCM(a,b) = Produkt aller Primfaktoren mit maximalen Exponenten. Bruchvereinfachung: Zähler und Nenner durch GCD dividieren. Eulers Totientenfunktion: φ(n) = n × ∏(1 - 1/p) für jeden bestimmten Primfaktor p. Bestimmung perfekter Quadrate: n ist ein perfektes Quadrat, wenn alle Primfaktor-Exponenten gerade sind. Anzahl der Teiler: (e₁+1)(e₂+1)...(eₖ+1), wobei eᵢ die Exponenten sind.

Das Sieb des Eratosthenes findet effizient alle Primzahlen bis N. Algorithmus: Erstellen Sie ein boolesches Array [2..N], markieren Sie alle als wahr. Für jede unmarkierte Zahl p beginnend bei 2: Markieren Sie alle Vielfachen von p (p², p²+p, ...) als zusammengesetzt. Übrige unmarkierte Zahlen sind Primzahlen. Zeit: O(n log log n), Speicher: O(n). Optimierungen: Beginnen Sie das Markieren bei p² (kleinere Vielfache sind bereits markiert), überprüfen Sie nur ungerade Zahlen nach 2. Für N = 10^6: ~78.498 Primzahlen. Für N = 10^9: benötigt segmentiertes Sieb zur Speicherreduktion. Wird in Wettkampfprogrammierung und Zahlentheorie verwendet.

Eulers Totient φ(n) zählt die ganzen Zahlen von 1 bis n, die teilerfremd mit n sind (teilen keinen gemeinsamen Faktor). Wichtige Eigenschaften: φ(1) = 1. Für Primzahl p: φ(p) = p − 1. Für Primzahlpotenz: φ(p^k) = p^k − p^(k-1). Für teilerfremd a, b: φ(a×b) = φ(a)×φ(b) (multiplikativ). Allgemein: φ(n) = n × ∏(1 − 1/p) für jeden bestimmten Primfaktor p, der n teilt. Beispiel: φ(12) = 12 × (1−1/2) × (1−1/3) = 12 × 1/2 × 2/3 = 4. Mit 12 teilerfremde ganze Zahlen: {1, 5, 7, 11}. Verwendet bei: RSA (Eulers Theorem: a^φ(n) ≡ 1 mod n), Gruppentheorie.

Eine perfekte Zahl ist gleich der Summe ihrer echten Teiler (Teiler ohne die Zahl selbst). Beispiele: 6 = 1+2+3. 28 = 1+2+4+7+14. 496. 8128. Nur 51 perfekte Zahlen sind bekannt; alle bekannten sind gerade. Mersenne-Primzahlen: n = 2^(p-1) × (2^p - 1) ist perfekt, wenn (2^p - 1) Primzahl ist (Mersenne-Primzahl). Verwandte Konzepte: Abundante Zahl: σ(n) > 2n (Summe aller Teiler > 2×Zahl). Defiziente Zahl: σ(n) < 2n. Befreundete Zahlen: Paar, bei dem σ(a) = b+a und σ(b) = a+b. Beispiel: 220 und 284.