Wann hat eine Zahl genau k Nullen am Ende? Natürlich wenn \(10^k\) ein Teiler und \(10^{k+1}\) kein Teiler der Zahl ist.
Wann ist eine Zahl durch \(10^k\) teilbar? Wenn sie durch \(2^k\) und \(5^k\) teilbar ist.
Was heißt das für uns?
Wir suchen die maximalen Zahlen a,b sodass
$$2^a | n!$$
Und
$$5^b | n!$$
Ich setze hier \( n=1000000\)
Dann teilt offenbar \( 10^{min(a,b)} \) deine Fakultät. Und somit ist min(a,b) die Anzahl der Nullen am Ende.
Der Primfaktor 2 kommt in der Zerlegung von n! sicher häufiger vor als 5, denn jede zweite Zahl im Produkt bringt mindestens eine 2 als Faktor mit, aber nur jede fünfte mindestens eine 5.
Also: a≥b
Wir suchen deshalb nur das größte b mit
$$ 5^b | n! $$
Das berechnet man so:
$$ b = \sum_{k=1}^\infty \left\lfloor \frac{n}{5^k} \right\rfloor$$
Überlege dir mal wieso das so ist.
