Разложение числа на простые множители: сомножители, алгоритм и код

Сомножитель — это каждое из чисел, которые перемножают в произведении: в записи 2 * 3 * 7 = 42 сомножители — 2, 3 и 7. Разложить число на простые множители — значит записать его произведением сомножителей, каждый из которых простое число. Ниже — теорема, которая гарантирует, что такое разложение единственно, ручные способы, код на Python с оценкой сложности и два применения: НОД/НОК и криптография RSA.

Мини-словарь: множитель, сомножитель, делитель

Термины близкие, но не одинаковые. Разведу их на одном числе 42.

Слова «множитель» и «сомножитель» в современной школьной и бытовой речи почти синонимы. В классической терминологии у двух чисел в произведении были отдельные названия: «множимое» и «множитель», а «сомножители» — общее имя для обоих. В натуральных числах любой сомножитель произведения является его делителем, но делителей обычно больше, чем простых множителей: 6 и 14 делят 42, а в каноническую запись не входят.

Простое число — натуральное число больше 1, у которого ровно два делителя: 1 и оно само. Составное — натуральное число больше 1, у которого делителей больше двух. Число 1 не простое и не составное.

Основная теорема арифметики

Любое натуральное число n > 1 раскладывается в произведение простых множителей, и это разложение единственно с точностью до порядка сомножителей.

Отсюда каноническая запись: n = p1^a1 * p2^a2 * … * pk^ak, где p1 < p2 < … < pk — простые, а показатели a1…ak — натуральные. Примеры:

• 84 = 2^2 * 3 * 7;
• 315 = 3^2 * 5 * 7;
• 360 = 2^3 * 3^2 * 5;
• 97 = 97 (простое число — это разложение из одного сомножителя).

Последний пример важен: разложение не обязано содержать два и больше сомножителей. Единственность, кстати, — главная причина, по которой 1 не считают простым: иначе 6 = 2 * 3 = 1 * 2 * 3 = 1 * 1 * 2 * 3, и разложение перестало бы быть единственным даже с точностью до перестановки.

Как разложить число вручную

Столбиком. Слева пишут число, справа — наименьший простой делитель, делят, результат переносят вниз и повторяют, пока слева не останется 1. Для 84:

84 | 2
42 | 2
21 | 3
 7 | 7
 1 |

Правая колонка дает ответ: 84 = 2 * 2 * 3 * 7 = 2^2 * 3 * 7. Порядок сомножителей в ответе значения не имеет, но в канонической записи их ставят по возрастанию.

Деревом. Число раскладывают на любую пару сомножителей, затем каждую ветку — дальше, пока в листьях не останутся простые. Для 315: 315 = 9 * 35, затем 9 = 3 * 3 и 35 = 5 * 7. Листья 3, 3, 5, 7 дают 315 = 3^2 * 5 * 7. Если начать с 315 = 5 * 63, листья будут те же — это и есть единственность из теоремы.

Проверять делимость на 2, 3 и 5 быстро помогают признаки: на 2 — последняя цифра четная, на 3 — сумма цифр делится на 3, на 5 — число оканчивается на 0 или 5.

Алгоритм перебором до корня

Ключевое наблюдение: если n составное, у него есть делитель не больше √n. Если n = a * b и оба больше √n, то a * b > n — противоречие. Поэтому пробные делители достаточно перебирать, пока d * d <= n. Все, что осталось после этого и больше 1, — простое.

Прогон руками для 84:

1. d = 2: 84 -> 42 -> 21 (2 вошло дважды).
2. d = 3: 3 * 3 = 9 <= 21, 21 -> 7.
3. d = 5: 5 * 5 = 25 > 7, цикл заканчивается.
4. Остаток 7 > 1 — это последний простой множитель.

Тот же алгоритм на Python (проверено на Python 3.14):

def factorize(n: int) -> dict[int, int]:
    """Разложение n >= 2 на простые множители перебором до корня."""
    if n < 2:
        raise ValueError("нужно целое n >= 2")
    factors: dict[int, int] = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors[d] = factors.get(d, 0) + 1
            n //= d
        d += 1 if d == 2 else 2   # после 2 проверяем только нечетные
    if n > 1:                     # остаток больше корня - простое число
        factors[n] = factors.get(n, 0) + 1
    return factors


def canonical(factors: dict[int, int]) -> str:
    parts = []
    for p, k in sorted(factors.items()):
        parts.append(str(p) if k == 1 else f"{p}^{k}")
    return " * ".join(parts)


for n in (84, 315, 360, 97, 1001, 1024, 600851475143):
    print(n, "=", canonical(factorize(n)))

Вывод:

84 = 2^2 * 3 * 7
315 = 3^2 * 5 * 7
360 = 2^3 * 3^2 * 5
97 = 97
1001 = 7 * 11 * 13
1024 = 2^10
600851475143 = 71 * 839 * 1471 * 6857

Разбор. Внутренний while делит на d, пока делится, поэтому в словарь попадают только простые: к моменту проверки d = 9 все тройки уже вынесены, и 9 на остаток уже не делится. Четные d после 2 код вообще не проверяет, а в варианте с шагом 1 (ниже) d = 4 не сработает по той же причине — двойки вынесены раньше. Условие d * d <= n проверяется по уже уменьшенному n, поэтому после выноса малых множителей цикл заканчивается раньше. Деление целочисленное (//), без перехода в float и потери точности на больших числах.

Типичная ошибка: потерян последний множитель

Если забыть ветку if n > 1, пропадает простой множитель больше корня из остатка:

def factorize_bad(n):
    factors = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors[d] = factors.get(d, 0) + 1
            n //= d
        d += 1
    return factors          # забыли остаток n > 1

print(factorize_bad(14), factorize_bad(97), factorize_bad(84))

{2: 1} {} {2: 2, 3: 1}

Для 14 потеряна 7, для простого 97 результат вообще пустой, для 84 снова нет 7. Исправление — вернуть проверку остатка, как в рабочей версии выше.

Сложность: почему перебор не масштабируется

В худшем случае (n простое или равно произведению двух близких простых) цикл доходит до √n. После двойки проверяются только нечетные d, это около √n / 2 делений. Замер на Python 3.14 в docker (время зависит от машины):

import time

def trial_divisions(n):
    """Сколько делений делает перебор (2, затем нечетные) до корня."""
    count, d = 0, 2
    while d * d <= n:
        count += 1
        while n % d == 0:
            n //= d
            count += 1
        d += 1 if d == 2 else 2
    return count

for n in (10**6 + 3, 10**9 + 7, 10**12 + 39, (10**6 + 3) * (10**6 + 33), 2**40):
    t = time.perf_counter()
    c = trial_divisions(n)
    print(f"{n:>16}  делений: {c:>8}  время: {time.perf_counter() - t:.3f} c")

         1000003  делений:      500  время: 0.000 c
      1000000007  делений:    15811  время: 0.001 c
   1000000000039  делений:   500000  время: 0.084 c
   1000036000099  делений:   500003  время: 0.075 c
   1099511627776  делений:       41  время: 0.000 c

Первые четыре числа — простые или произведение двух простых около миллиона, поэтому перебор идет до корня. У 2^40 все множители маленькие: 41 деление. Отсюда граница оценки: O(√n) — это худший случай, а на числах с малыми множителями перебор заканчивается быстро.

Важная деталь: O(√n) выглядит скромно, но размер входа — это количество цифр, а не само n. Для числа из b бит √n = 2^(b/2), то есть время растет экспоненциально от длины записи. Каждые 2 лишних десятичных знака в n увеличивают худший случай примерно в 10 раз.

Для чисел до 10^18 на практике берут более быстрые методы (ро-алгоритм Полларда плюс тест простоты Миллера — Рабина), в Python они есть, например, в sympy.factorint. Для сотен цифр известны только субэкспоненциальные классические алгоритмы, и на ключах RSA современной длины их не хватает.

Применение 1: НОД и НОК через разложение

Если оба числа разложены канонически, НОД — произведение общих простых в минимальной степени, НОК — произведение всех простых в максимальной степени. Пример: 196 = 2^2 * 7^2, 260 = 2^2 * 5 * 13. Общее простое только 2, поэтому НОД = 2^2 = 4, а НОК = 2^2 * 5 * 7^2 * 13 = 12740.

В Python Counter делает это операторами: & берет минимум степеней, | — максимум:

from collections import Counter
from math import gcd, lcm, prod

def factorize(n):
    f, d = Counter(), 2
    while d * d <= n:
        while n % d == 0:
            f[d] += 1
            n //= d
        d += 1 if d == 2 else 2
    if n > 1:
        f[n] += 1
    return f

def from_factors(f):
    return prod(p ** k for p, k in f.items())

a, b = factorize(196), factorize(260)
print(dict(a), dict(b))
print("НОД:", from_factors(a & b), gcd(196, 260))   # & - минимум степеней
print("НОК:", from_factors(a | b), lcm(196, 260))   # | - максимум степеней
print("НОД/НОК 15 и 40:", from_factors(factorize(15) & factorize(40)),
      from_factors(factorize(15) | factorize(40)))

{2: 2, 7: 2} {2: 2, 5: 1, 13: 1}
НОД: 4 4
НОК: 12740 12740
НОД/НОК 15 и 40: 5 120

Результат совпадает со стандартными math.gcd и math.lcm (lcm доступна с Python 3.9). Граница метода: через разложение удобно считать вручную и объяснять, но для больших чисел НОД вычисляют алгоритмом Евклида, которому разложение не нужно, — как раз потому, что разложение дорогое.

Применение 2: почему на трудности разложения держится RSA

В RSA открытый ключ — это модуль n = p * q (два больших простых) и экспонента e. Закрытая экспонента d вычисляется из φ(n) = (p — 1) * (q — 1), а φ(n) легко получить, только зная p и q. Перемножить два простых быстро, разложить их произведение обратно на современных длинах ключа известными классическими методами практически нельзя.

Учебная модель на крошечных числах (не шифрование, а демонстрация идеи):

# Учебная RSA на крошечных числах: НЕ для реального шифрования
p, q = 61, 53
n = p * q                  # открытый модуль
phi = (p - 1) * (q - 1)    # знает только тот, кто знает p и q
e = 17                     # открытая экспонента, взаимно проста с phi
d = pow(e, -1, phi)        # закрытая экспонента (Python 3.8+)
m = 65
c = pow(m, e, n)
print(f"n={n} phi={phi} d={d}")
print("шифр:", c, "расшифровка:", pow(c, d, n))

# Атакующий видит только (n, e) - и раскладывает n перебором
f = next(x for x in range(2, n) if n % x == 0)
d_found = pow(e, -1, (f - 1) * (n // f - 1))
print("найден множитель:", f, "d атакующего:", d_found)

n=3233 phi=3120 d=2753
шифр: 2790 расшифровка: 65
найден множитель: 53 d атакующего: 2753

Модуль 3233 раскладывается мгновенно, и атакующий получает тот же закрытый ключ 2753. Поэтому реальные модули берут длиной от 2048 бит: перебору там нужно около 10^308 делений (строка таблицы выше).

Граница этого примера: «учебник RSA» без паддинга небезопасен даже при длинном ключе — одинаковые сообщения дают одинаковый шифр, возможны атаки на малые сообщения. В реальном коде используют проверенные библиотеки со схемами OAEP (шифрование) и PSS (подпись) и не пишут RSA вручную. Кроме того, трудность разложения — не доказанный факт, а отсутствие известного быстрого классического алгоритма; алгоритм Шора решил бы задачу на достаточно большом квантовом компьютере, поэтому развивается постквантовая криптография.

Выводы

• Сомножитель — любое число в произведении; простой множитель — сомножитель, который является простым; делителей у числа обычно больше, чем простых множителей.
• Основная теорема арифметики гарантирует, что разложение числа больше 1 на простые единственно с точностью до порядка; каноническая запись — степени простых по возрастанию.
• Перебор делителей до √n с проверкой остатка корректно раскладывает любое число, но в худшем случае требует около √n / 2 делений — экспоненциально от числа цифр.
• Через разложение НОД берет минимум степеней общих простых, НОК — максимум степеней всех простых; для больших чисел НОД считают алгоритмом Евклида.
• RSA опирается на то, что разложить произведение двух больших простых известными классическими методами практически невозможно.

Где применяется / связь с практикой

FAQ

Можно ли разложить на простые множители отрицательное число или ноль?
Отрицательное число записывают как -1, умноженное на разложение модуля: -84 = -1 * 2^2 * 3 * 7. У нуля разложения нет: произведение простых чисел никогда не равно 0. Число 1 по соглашению считают пустым произведением — в нем нет ни одного простого множителя.

Чем разложение на множители отличается от разложения многочлена?
Идея та же — представить объект произведением неразложимых частей, но для многочленов неразложимость зависит от поля коэффициентов: x^2 + 1 не раскладывается над действительными числами и раскладывается над комплексными.

Как быстро разложить сразу все числа до N?
Решетом с сохранением наименьшего простого делителя для каждого числа: после предподсчета за время около N * log log N разложение любого числа до N идет делением на сохраненный делитель за O(log n) шагов.