La formula di Legendre e la sua utilità nelle applicazioni

In teoria dei numeri, l'identità di Legendre, fornisce l'esponente della maggiore potenza di un numero primo ${\displaystyle p}$ che divide il fattoriale ${\displaystyle n!,}$dove ${\displaystyle n\geq 1}$ è un intero. Ciò che si vuole ricavare è la scomposizione di n! ovvero:

Dove R è l'intero dispari, e v è chiamata valutazione p-atica di n! e si ricava come segue:

Questa formula è chiamata appunto Formula di Legendre . Per le applicazioni c'è una formula alternativa di grande utilità :

Quindi tramite operazioni di conteggio dei bit all’interno di un numero, espresso in base 2, è possibile ottenere quanto richiesto.