Формула Лежандра нужно для того, чтобы узнавать степень вхождения простого числа в факториал. Вычислить значение степени вхождения простого числа р в число n! можно за асимптотику О(log(p) n). Сама формула выглядит так: $$$v(n!) = [n / p^1] + [n / p^2] + [n / p^3] + ...$$$ Нетрудно доказать, что она верна.