Математика · объяснение и практика
Как посчитать показатель простого числа в факториале
Как найти точный показатель простого множителя в факториале, учесть дополнительные вклады квадратов простого и применять результат к целым факториальным отношениям.

В теме Теория чисел: углубление · Учебная карта
В маршруте Новые структуры целой арифметики · 10 тем
Главная мысль
Показатель простого p в n! равен сумме целых частей n/p, n/p², n/p³ и далее. Каждая степень p учитывает ещё один слой повторного появления этого простого множителя.
Почему недостаточно числа кратных
В произведении от одного до двадцати кратные трём встречаются шесть раз. Но множитель девять содержит две тройки, как и восемнадцать. Поэтому показатель тройки в 20! больше шести. Первый подсчёт учитывает по одной тройке в каждом кратном, а следующий должен добавить вторые тройки из кратных девяти.
Именно поэтому складывают целые части делений на последовательные степени простого. Кратных p² среди чисел до n столько, сколько целая часть n/p². Они уже учтены на первом слое, но теперь получают необходимый дополнительный вклад. Кратные p³ добавляются ещё раз. Повторный учёт здесь намеренный и соответствует нескольким одинаковым простым множителям.
Послойный подсчёт без огромного произведения
Для 20! и p=3 имеем шесть кратных трём, два кратных девяти и ни одного кратного двадцати семи. Показатель равен восьми. Сам факториал вычислять не пришлось. Сумма всегда конечна: как только очередная степень p превосходит n, её целая часть и все дальнейшие вклады равны нулю.
Для отношения факториалов показатели вычитаются. Например, в числе сочетаний C(n,k)=n!/(k!(n−k)!) показатель p получается разностью трёх таких сумм. Для корректного целого сочетания результат неотрицателен. Если в произвольном отношении он отрицателен хотя бы для одного простого, отношение не является целым.
Пример
Каков показатель двойки в 18!?
Складываем целые части: 18/2 даёт 9, 18/4 даёт 4, 18/8 даёт 2, 18/16 даёт 1. Итого 16. Степень 32 уже больше 18 и ничего не добавляет.
Простое основание и составной делитель
Формула относится к простому p. Для наибольшей степени составного числа сначала раскладывают его на простые. Чтобы понять, сколько раз делится на двенадцать, сравнивают запас двоек и троек: на каждую двенадцатку нужны две двойки и одна тройка. Ответ задаёт меньший из соответствующих доступных количеств.
Число нулей в конце десятичной записи факториала — частный случай с основанием десять. Оно требует пар двойка-пятёрка, а не просто количества множителей десять в исходном списке. Поскольку двоек в факториале не меньше, ограничивают пятёрки. Объяснение через показатели позволяет перенести тот же принцип на другие основания без придумывания новой формулы.
От чтения к действию
А теперь — вы
Частые вопросы
Что делать при n=0?
Поскольку 0!=1, показатель любого простого равен нулю. В сумме все целые части также нулевые.
Почему кратные квадрату простого учитывают дважды?
В них действительно есть как минимум два множителя p: первый посчитан на слое p, второй добавлен на слое p².
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как разложение на простые задаёт сумму всех положительных делителей
Как сумма всех положительных делителей раскладывается в произведение геометрических сумм, почему требуется разложение на различные простые и как отделить собственные делители.
Открыть темуКак выбрать наименее затратное целое решение по знаку коэффициента
Как выбрать оптимальную пару из целых решений: подставить полное семейство в линейную стоимость, определить направление изменения и не спутать допустимость с минимумом.
Открыть тему