Разложение числа на множители: перебор делителей до корня

Постановка задачи

Дано натуральное число n. Нужно представить его в виде произведения простых множителей: 360 = 2·2·2·3·3·5. Контракт этой функции ограничен целыми n ≥ 2. Для 1 можно отдельно договориться о пустом списке множителей с произведением 1, но здесь такой вход отклоняется. У нуля нет конечного разложения в произведение простых чисел; у отрицательного числа отдельно учитывают знак −1.

Идея алгоритма

Будем делить n нацело на каждый делитель d, начиная с 2. Каждый найденный делитель — это простой множитель (все меньшие простые делители уже удалены из оставшегося числа). Если после деления остаток больше 1 — он сам простой и является последним множителем.

Почему хватает проверки до квадратного корня? У составного числа обязательно есть делитель не больше квадратного корня: иначе произведение двух множителей превысило бы само число. У квадрата делитель может быть в точности равен корню. Значит, перебор d от 2 до isqrt(n) исчерпывает все случаи. Такое обоснование важно: без него оценка скорости остаётся голословной.

Пример 1. Основная функция

import math

def factorize(n):
    if not isinstance(n, int):
        raise TypeError('n должен быть целым числом')
    if n < 2:
        raise ValueError('разложение определено только для n >= 2')
    factors = []
    d = 2
    while d <= math.isqrt(n):
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return factors

print(factorize(360))   # [2, 2, 2, 3, 3, 5]
print(factorize(97))    # [97] — простое

Разберём 360 по шагам: пока делится на 2 — делим (три раза, получаем 45); на 3 — два раза (остаётся 5); после этого d увеличивается до 4, но isqrt(5) равно 2, поэтому внешний цикл заканчивается. Остаток 5 добавляется отдельным последним шагом. Внутренний while вычерпывает делитель полностью, поэтому множители идут по неубыванию и каждый записывается столько раз, сколько входит в разложение. Для простого 97 цикл не находит делителей, и остаток 97 дописывается в конец.

Пример 2. Проверка простоты

Среди целых чисел n ≥ 2 число простое, когда его разложение состоит из одного множителя — его самого. Единица, ноль и отрицательные числа простыми не являются: is_prime для них возвращает False, хотя factorize использует более узкий контракт.

def is_prime(n):
    if not isinstance(n, int):
        raise TypeError('n должен быть целым числом')
    if n < 2:
        return False
    return factorize(n) == [n]

print(is_prime(97))   # True
print(is_prime(91))   # False: 91 = 7 * 13

Классическая ловушка — 91 кажется простым, но 91 = 7·13. Алгоритм её «видит»: после деления на 7 остаётся 13, который больше isqrt(13), поэтому попадает в ответ как последний множитель.

Внешняя граница пересчитывается по оставшемуся n, а не по исходному числу: после удаления множителей работа сокращается. В худшем случае для большого простого N требуется порядка √N пробных делений. Это число проверок, а не обещание постоянного времени каждой операции над сколь угодно большим целым. Для очень больших чисел применяют другие алгоритмы; здесь время не измеряется.

Граничные случаи

1. n = 2 и n = 3 — минимальные допустимые значения; оба простые, ответ [2] и [3].
2. Полные квадраты: 36 = 2·2·3·3, 49 = 7·7 — делитель, равный корню, обрабатывается корректно, потому что условие цикла d <= isqrt(n).
3. n меньше 2 — ValueError; это часть контракта функции.
4. Степени двойки: 1024 = 2 в десятой — ответ [2, 2, …] десять раз.

Проверь себя

1. Что вернёт factorize(12)? Ответ: [2, 2, 3] — 12 = 4·3, и двойка входит дважды.
2. Что произойдёт при factorize(1)? Ответ: ValueError — вне допустимой области n >= 2.
3. Разложите вручную 100 и сверьте с алгоритмом. Ответ: 100 = 2·2·5·5, функция вернёт [2, 2, 5, 5].
4. Почему перебор останавливается на корне, а не на n? Ответ: большему делителю всегда парен меньший корня, а меньшие уже проверены; иначе в худшем случае число проб выросло бы с порядка √N до порядка N.

Кратко о главном

Разложение на множители строится делением нацело от 2 до целочисленного корня из n. У factorize допустимая область — целые n ≥ 2: меньшие целые отклоняются через ValueError, неверный тип — через TypeError. Проверка is_prime для целых меньше двух возвращает False. Множители выходят по неубыванию, их произведение всегда равно исходному числу — этим удобно проверять алгоритм.

Связанные материалы

• Основы программирования на Python
• Что такое разложение на простые множители
• Простые и составные числа

Источники и материалы

• math — Mathematical functions (Python 3.15.2)
• Errors and Exceptions (Python Tutorial, 3.15.2)
• Python: точное определение целочисленного корня