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