[tex]n! = 1 \cdot 2 \cdot 3 \cdot ... \cdot n[/tex]
Deoarece [tex]10 = 2 \cdot 5[/tex], avem [tex]\textrm{numarul de zerouri de la sfarsitul lui n!} = min(\textrm{Exponentul lui 5}, \textrm{Exponentul lui 2})[/tex].
Deoarece exponentul lui 2 este mai mare decat exponentul lui 5 in n!(pentru ca in intervalul [1,n] sunt mai multi multiplii de 2 decat de 5), numarul de zerouri este egal cu exponentul lui 5 in n!
Acum, trebuie sa aflam exponentul lui 5 in n!
[tex]n! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10 \cdot ... \cdot n[/tex]
In acest produs, sunt (n div 5) multiplii ai lui 5, ii putem aduna la s.
Acum si pentru [tex](n \: div \: 5)! [/tex]
[tex](n \: div \: 5)! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot \cdots \cdot (n \: div \: 5)[/tex]
(1 vine de la 5, 2 de la 10, 3 de la 15, 4 de la 20, 5 de la 25, 6 de la 30 s.a.m.d.), si de aici la suma se mai aduna (n div 5) div 5 = n div 25 pentru [tex]5^2[/tex](trebuie sa adunam 1 + 1, dar pentru [tex]5^1[/tex] i-am adunat la inceput)
Apoi in
[tex](n \: div \: 25)! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdots (n \: div \: 25)[/tex]
De unde mai adunam (n div 25) div 5 = n div 125 la suma pentru [tex]5^3[/tex](trebuie sa adunam 1 + 1 + 1, dar pentru [tex]5^2[/tex] si [tex]5^1[/tex] i-am adunat deja)
...
In final, exponentul lui 5 in n! se poate scrie
[tex]\displaystyle n \: div \: 5 + n \: div \: 25 + n \: div \: 125 + n \: div \: 625 + \cdots = \sum_{k=1}^{\infty} n \: div \: (5^k)[/tex].
Nu se considera puterile lui 5 mai mari decat n, deci un algoritm posibil pentru determinarea numarului de zerouri de la sfarsitul lui n! este cel dat de tine.
