Факторизация факториала

Положительное целое число, для расчета факториала

Полученный результат

Название темы, для несведующих людей, может быть немного запутанным, и даже похже на тафтологическое выражение "масло масленное". На самом деле, под название темы подразумевается разложение факториала на простейшие множители с степенями.

Зачем это надо?

Кто сталкивался с факториалами, знают что уже при значении 20, факториал достигает огромных значений 2432902008176640000

При факториале 100 значение получается еще больше, и возникает резонный вопрос а как можно представить факториал такого числа в более удобной и наглядной форме? Во первых это красиво, а во вторых полезно, так как отвечает еще и на попутно возникающий вопрос, например , сколько двоек/пятерок/семерок в факториале числа 2015?

Что бы решить такую задачу, не надо вычислять факториал от числа 2015, а потом искать число целочисленных делений на тройку например , достаточно знать формулу по который рассчитывается число вхождений.

Итак если число p простое, то количество вхождений в факториал числа m, вычисляется как

$S=[\frac{m}{p}]+[\frac{m}{p^2}]+[\frac{m}{p^3}]+....[\frac{m}{p^k}]$

где квадратные скобки означают что берётся целая часть от деления.

Самый простой пример, сколько раз входит число 3 в факториал 50?

Рассчитываем:

$S=[\frac{50}{3}]+[\frac{50}{9}]+[\frac{50}{27}]+[\frac{50}{81}]$

то есть тройка встречается в числе 50! ровно 22 раза.

Теперь несложно, пробежавшись по всем простым числам от 1 до 50, для каждого из них узнать количество вхождений.

Окончательный ответ, в виде факторизации факториала пятидести будет иметь вид.

$S=[\frac{50}{3}]+[\frac{50}{9}]+[\frac{50}{27}]+[\frac{50}{81}]$

Решим еще один пример, часто встречающийся.

На какое количество нулей оканчивается факториал числа 306?

Для решения такой задачи надо знать что 10 это произвдение двух простых чисел 2 и 5.

Таким образом узнав количество вхождений пятерки в факториал ( количество вхождений двойки, естественно будет больше), мы узнаем какое количество нулей будет в факториала 306.

Ответ: на 75 нулей будет оканчиватся заданный факториал.

Удачных расчетов!