Разложение на простые множители и делители
Разложите N на степени простых и подсчитайте делители
«Разложение на простые множители и делители» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Разложите N на множители
Каждое целое число больше 1 единственным образом представляется как произведение простых чисел. Поиск этого разложения — его разложение на простые множители — помогает решать многие задачи теории чисел. 🧩
Идея пробного деления
Извлекайте наименьший простой делитель n, делите на него и повторяйте. Этот простой метод пробного деления постепенно уменьшает n до 1.
Цикл до квадратного корня
Проверяйте делители i, пока i*i не превышает n. После квадратного корня может остаться не более одного простого множителя.
while i * i <= n:
...Извлеките каждый множитель
Пока i делит n, продолжайте деление и записывайте i. Так вы получите полную степень этого простого множителя, прежде чем перейти дальше.
while n % i == 0:
factors.append(i)
n //= iОставшийся простой множитель
После цикла, если n всё ещё больше 1, само n является простым множителем, большим квадратного корня. Добавьте его один раз.
if n > 1:
factors.append(n)Полный алгоритм
Вместе эти шаги дают разложение на множители за время O(sqrt n), возвращая каждый простой множитель с полной кратностью и в правильном порядке.
def factorize(n):
f, i = [], 2
while i * i <= n:
while n % i == 0:
f.append(i); n //= i
i += 1
if n > 1: f.append(n)
return fСгруппируйте множители по степеням
Для подсчёта делителей нужно хранить каждый простой множитель вместе с его показателем степени, например 2^3, а не 2,2,2. Счётчик аккуратно подсчитывает повторы.
from collections import Counter
exp = Counter(factorize(n))Формула количества делителей
Если n равно p1^a, умноженному на p2^b, количество делителей равно (a+1), умноженному на (b+1). Для каждого показателя степени есть один дополнительный вариант.
Подсчёт делителей
Перемножьте единицу, прибавленную к каждому показателю степени, для всех простых чисел. Так Вы получите общее количество делителей, не перечисляя их.
count = 1
for e in exp.values():
count *= (e + 1)Сумма делителей
Связанная формула вычисляет сумму делителей с помощью геометрического ряда для каждого простого числа. Знание этой формулы помогает решать задачи о совершенных числах и аликвотах.
Ускорение с помощью решета
Если требуется выполнить много разложений, заранее вычислите наименьший простой делитель каждого числа с помощью решета. Тогда разложение каждого числа по запросу займёт log n шагов.
Быстрая проверка
Примените формулу подсчёта делителей к конкретному числу.
Итоги
Теперь Вы умеете раскладывать N на множители методом пробного деления за O(sqrt n), выделять оставшийся простой множитель, группировать показатели степеней и подсчитывать делители с помощью формулы произведения. ✅
Часто задаваемые вопросы
Урок «Разложение на простые множители и делители» бесплатный?
Да — полный текст урока «Разложение на простые множители и делители» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Разложение на простые множители и делители»?
Разложите N на степени простых и подсчитайте делители Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Разложение на простые множители и делители»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- GCD, LCM и алгоритм Евклида
- Проверка простоты до sqrt(n)
- Решето Эратосфена
- Разложение на простые множители и делители