Primfaktorzerlegung und Teiler
Zerlegen Sie N in Primzahlpotenzen und zählen Sie die Teiler
Primfaktorzerlegung und Teiler ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
N in Faktoren zerlegen
Jede ganze Zahl größer als 1 ist ein eindeutiges Produkt von Primzahlen. Diese Zerlegung, ihre Primfaktorzerlegung, eröffnet viele Probleme der Zahlentheorie. 🧩
Die Idee der Probedivision
Ziehen Sie die kleinste Primzahl heraus, die n teilt, teilen Sie sie heraus und wiederholen Sie den Vorgang. Diese einfache Probedivision zerlegt n schrittweise bis auf 1.
Bis zur Wurzel iterieren
Prüfen Sie Teiler i, solange i*i höchstens n ist. Jenseits der Quadratwurzel kann höchstens ein Primfaktor übrig bleiben.
while i * i <= n:
...Jeden Faktor extrahieren
Solange i n teilt, teilen Sie weiter und speichern Sie i. So erfassen Sie die vollständige Potenz dieser Primzahl, bevor Sie fortfahren.
while n % i == 0:
factors.append(i)
n //= iDer verbleibende Primfaktor
Wenn n nach der Schleife noch größer als 1 ist, ist n selbst ein Primfaktor größer als die Quadratwurzel. Fügen Sie ihn einmal hinzu.
if n > 1:
factors.append(n)Die vollständige Routine
Zusammen ergibt dies eine Faktorisierung in O(sqrt n)-Zeit und liefert jede Primzahl mit ihrer vollständigen Vielfachheit in der richtigen Reihenfolge zurück.
def factorize(n):
f, i = [], 2
while i * i <= n:
while n % i == 0:
f.append(i); n //= i
i += 1
if n > 1: f.append(n)
return fZu Potenzen gruppieren
Für die Bestimmung der Teileranzahl benötigen Sie jede Primzahl mit ihrem Exponenten, also etwa 2^3 statt 2,2,2. Ein Counter zählt die Wiederholungen übersichtlich.
from collections import Counter
exp = Counter(factorize(n))Die Teilerformel
Wenn n = p1^a mal p2^b ist, beträgt die Anzahl der Teiler (a+1) mal (b+1). Für jeden Exponenten gibt es eine zusätzliche Auswahlmöglichkeit.
Teiler zählen
Multiplizieren Sie für alle Primzahlen jeweils den um eins erhöhten Exponenten. Das ergibt die gesamte Teileranzahl, ohne die Teiler einzeln aufzulisten.
count = 1
for e in exp.values():
count *= (e + 1)Teilersumme
Eine verwandte Formel summiert die Teiler mithilfe der geometrischen Reihe jeder Primzahl. Wenn Sie sie kennen, können Sie Probleme zu vollkommenen Zahlen und Aliquotenfolgen lösen.
Mit einem Sieb schneller werden
Bei vielen Faktorisierungen können Sie den kleinsten Primfaktor jeder Zahl mit einem Sieb vorberechnen. Danach lässt sich jede Abfrage in log n Schritten faktorisieren.
Schnelltest
Wenden Sie die Formel zur Bestimmung der Teileranzahl auf eine konkrete Zahl an.
Rückblick
Sie können N nun durch Probedivision in O(sqrt n) faktorisieren, den verbleibenden Primfaktor erfassen, Exponenten gruppieren und die Teiler mit der Produktformel zählen. ✅
Lerne Python mit einem KI-Tutor — kostenlos
Schreibe und führe echten Code in deinem Browser aus, bekomme sofortige Hilfe von einem 24/7 KI-Tutor und setze dein Lernen im Web oder in der App fort.
- Kurse
- 30
- Lektionen
- 120
Häufig gestellte Fragen
Ist die Lektion „Primfaktorzerlegung und Teiler“ kostenlos?
Ja — der vollständige Text von „Primfaktorzerlegung und Teiler“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Primfaktorzerlegung und Teiler“?
Zerlegen Sie N in Primzahlpotenzen und zählen Sie die Teiler Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.
Wie lange dauert die Lektion „Primfaktorzerlegung und Teiler“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- GGT, KGV und der euklidische Algorithmus
- Primzahltest bis sqrt(n)
- Sieb des Eratosthenes
- Primfaktorzerlegung und Teiler