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 $\mathcal{O}(\sqrt{n})$ 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 ≤ $10^9$).

Ausgabe

Das Programm soll die Anzahl der Teiler von n ausgeben.

Beispiele