Legendreova formula je teorem u elementarnoj teoriji brojeva pomoću kojega se dobiva najveći eksponent kojim neki prosti broj
dijeli
Formula je nazvana prema francuskom matematičaru Adrienu-Marieu Legendreu. Ponegdje je poznata i kao de Polignacova formula po Alphonseu de Polignacu.
Strogi iskaz ovog teorema kaže da
ako
tada
za neki prosti
i prirodni broj
[1]
Kako je
umnožak cijelih brojeva od 1 do 500 slijedi da dobivamo barem jedan faktor od
u raspisu broja
za svaki višekratnik od
u skupu
kojih ima
No, svaki višekratnik od
daje dodatni faktor od
, a tih višekratnika ima
, pa ih moramo brojati još jednom (ukupno dva puta), svaki višekratnik od
daje dodatni faktor od
, a tih višekratnika ima
, pa ih moramo brojati još jednom (ukupno tri puta), itd.
Prema tome, ukupan broj faktora
koji se pojavljuju u raspisu broja
ima
jer će za neki
svi pribrojnici u toj sumi, počevši od
, biti manji od 1 pa ćemo ih zaokruživati na nulu.[2]
Želimo saznati koliko sedmica se pojavljuje u prostoj faktorizaciji broja
Primjerice, broj
očito nema sedmica u svom raspisu jer nije djeljiv sa sedam pa on neće na traženi način doprinijeti u raspisu broja
Dakle, tražimo koliko ima brojeva od 1 do 500 koji imaju barem jedan faktor
u svom raspisu, tj. one koji su djeljivi sa sedam. Njih ima
(svaki sedmi).
No, od tih 71, brojeva od 1 do 500 koji imaju barem dva faktora
(svaki 49.) u svom raspisu ima
pa njih treba brojati dva puta.
Slično, brojeva koji u svom raspisu imaju tri sedmice (svaki 343.) ima
pa njih treba brojati tri puta.
Prema tome, odgovor je
Taj zbroj je jednak
odnosno
što zaista daje