Legendre-képlet

Ez a szócikk nem tünteti fel a független forrásokat, amelyeket felhasználtak a készítése során. Emiatt nem tudjuk közvetlenül ellenőrizni, hogy a szócikkben szereplő állítások helytállóak-e. Segíts megbízható forrásokat találni az állításokhoz! Lásd még: A Wikipédia nem az első közlés helye.

Legendre 1808-ban fedezte fel hogyan kell kiszámítani, hogy mi az a legnagyobb hatványa egy ${\displaystyle p}$ prímszámnak, ami ${\displaystyle n}$ faktoriálisát osztja, eszerint ${\displaystyle p}$ kitevője:

${\displaystyle \varepsilon _{p}(n)=\sum _{k=1}^{\left\lfloor \log _{p}n\right\rfloor }\left\lfloor {\frac {n}{p^{k}}}\right\rfloor }$

${\displaystyle n}$-ig pontosan ${\displaystyle \left\lfloor {\frac {n}{p}}\right\rfloor }$ darab szám osztható ${\displaystyle p}$-vel (minden ${\displaystyle p}$-edik), mindegyik egyet ad ${\displaystyle p}$ kitevőjéhez. Továbbá ${\displaystyle \left\lfloor {\frac {n}{p^{2}}}\right\rfloor }$ darab osztható még ${\displaystyle p^{2}}$-tel is, ezek mind még egyet adnak ${\displaystyle p}$ kitevőjéhez. Az eljárást folytatva kapjuk ${\displaystyle p}$ kitevőjére a fenti képletet. Nyilván elég addig elmenni az összegzésben, amíg még ${\displaystyle p^{k}\leq n}$ teljesül, hiszen annál nagyobb ${\displaystyle p}$ hatványok már nem szerepelnek ${\displaystyle n!}$-ban.

Programozásban klasszikus példa, hogy adott ${\displaystyle n}$-re ${\displaystyle n!}$ hány darab nullára végződik. A fenti tétel erre megadja a választ, mivel triviálisan ${\displaystyle \varepsilon _{5}(n)\leq \varepsilon _{2}(n)}$, ezért a válasz rá ${\displaystyle \varepsilon _{5}(n)}$, ami ezáltal gyorsan és kevés memóriával kiszámítható, anélkül, hogy ${\displaystyle n!}$ értékét konkrétan kiszámítanánk, ami egy nagy szám.