Algorithmen und Datenstrukturen

Anzahl der Teiler mithilfe der Primfaktorisierung

Ein naiver Ansatz, die Anzahl der Teiler einer positiven ganzen Zahl n zu bestimmen, besteht darin, alle Werte von 1 bis einschließlich n zu durchlaufen und zu prüfen, wie viele davon n teilen.
Allerdings ist dieser Ansatz sehr langsam. Stattdessen lässt sich die Anzahl der Teiler von n anhand seiner Primfaktoren ermitteln (das Finden der Primfaktoren benötigt nur Zeit).
Man kann sich eine Zahl als Produkt ihrer Primfaktoren vorstellen:
Um die Anzahl der Teiler von n zu berechnen, nimmt man alle Exponenten der Primfaktoren, erhöht jeden um 1 und multipliziert diese Werte anschließend miteinander:
Diese Vorgehensweise ähnelt stark der Methode, mit der wir die Primfaktoren von n bestimmen:
n = ...
p, divisors = 1, 1          # Primfaktor und Anzahl der Teiler

while p * p <= n:           # solange p <= sqrt(n)
    p += 1                  # Erhöhe p in jedem Durchlauf um 1
    if n % p != 0:          # Nichts tun, wenn n nicht durch p teilbar ist
        continue
    
    exp = 0                 # Zähler für den Exponenten
    while n % p == 0:       # so oft wie möglich teilen
        n //= p
        exp += 1
    divisors *= exp + 1     # Produkt aktualisieren

if n > 1:                   # wenn p > sqrt(n), dann ist n selbst ein Primfaktor
    divisors *= 2           # füge n als Teiler mit Exponent 1 hinzu
print(divisors)

Aufgabe: Finde die Anzahl der Teiler von n

Gegeben ist eine ganze Zahl n. Bestimme, wie viele Teiler n besitzt.

Eingabe

Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl n (2 ≤ n ≤ ).

Ausgabe

Das Programm soll die Anzahl der Teiler von n ausgeben.

Beispiele

Eingabe
Ausgabe
8
4
17
2
2048
12
48
10
Bonus: Warum erhalten wir durch das Addieren von 1 zu den Exponenten und anschließendes Multiplizieren die Gesamtzahl der Teiler von n?
Die Grundidee hinter dieser Formel zur Bestimmung der Anzahl der Teiler von n ergibt sich aus der Kombination seiner Primfaktoren. Der Exponent jedes Faktors gibt an, wie oft dieser Faktor in einem Teiler von n vorkommen kann. Indem man zu jedem Exponenten 1 hinzufügt, schließt man auch die Möglichkeit ein, dass ein Faktor gar nicht verwendet wird (was den Teiler 1 einschließt) sowie die Fälle, in denen alle Faktoren vollständig genutzt werden (was n selbst einschließt). Durch das Multiplizieren dieser (Exponent + 1)-Werte jedes Primfaktors erhält man die Gesamtzahl möglicher Teiler von n.
 

Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue