Разложение на простые множители: способы и код на Python

Коротко

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

Любое натуральное число больше единицы раскладывается в произведение простых единственным способом (с точностью до порядка).

360 = 2³ · 3² · 5
84  = 2² · 3 · 7
97  = 97          (само простое)

Единственность разложения — фундамент теории чисел, и на нём держатся все формулы ниже.

Способ 1: перебор до корня

Основная идея: если n делится на d, то одновременно делится и на n/d. Один из этих двух множителей обязательно не превышает √n. Значит достаточно проверить делители до корня.

def factorize(n: int) -> dict[int, int]:
    """Возвращает {простое: степень}."""
    factors = {}

    # отдельно двойка, чтобы дальше идти с шагом 2
    while n % 2 == 0:
        factors[2] = factors.get(2, 0) + 1
        n //= 2

    d = 3
    while d * d <= n:
        while n % d == 0:
            factors[d] = factors.get(d, 0) + 1
            n //= d
        d += 2          # чётные уже не нужны

    # если что-то осталось — это простое больше корня
    if n > 1:
        factors[n] = factors.get(n, 0) + 1

    return factors


print(factorize(360))        # {2: 3, 3: 2, 5: 1}
print(factorize(97))         # {97: 1}
print(factorize(1000000007)) # {1000000007: 1}

Два момента, которые часто упускают.

Условие d * d <= n, а не d <= sqrt(n). Умножение точнее и быстрее вычисления корня с плавающей точкой, где возможны ошибки округления.

Проверка if n > 1 в конце. Если после всех делений что-то осталось, это простое число больше корня от исходного. Без этой строки разложение числа 14 дало бы только {2: 1}, потеряв семёрку.

Сложность O(√n): для числа 10¹² это миллион операций — приемлемо. Для 10¹⁸ уже миллиард, нужен другой метод.

Способ 2: решето с минимальным делителем

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

Модификация решета Эратосфена: вместо флага «простое / составное» храним наименьший простой делитель каждого числа.

def build_smallest_prime_factor(limit: int) -> list[int]:
    spf = list(range(limit + 1))     # spf[i] = i по умолчанию

    i = 2
    while i * i <= limit:
        if spf[i] == i:              # i простое
            for j in range(i * i, limit + 1, i):
                if spf[j] == j:      # ещё не помечено меньшим делителем
                    spf[j] = i
        i += 1

    return spf


spf = build_smallest_prime_factor(10 ** 6)


def factorize_fast(n: int) -> dict[int, int]:
    factors = {}
    while n > 1:
        p = spf[n]
        while n % p == 0:
            factors[p] = factors.get(p, 0) + 1
            n //= p
    return factors


print(factorize_fast(360))     # {2: 3, 3: 2, 5: 1}
print(factorize_fast(999983))  # {999983: 1}

Построение — O(n log log n), зато каждая последующая факторизация занимает O(log n): у числа не может быть больше log₂n простых множителей.

Проверка if spf[j] == j важна: она сохраняет наименьший делитель, не перезаписывая его большими.

Способ 3: ро-метод Полларда

Для чисел до 10¹⁸ перебор до корня уже не проходит. Ро-метод Полларда — вероятностный алгоритм, работающий примерно за O(n^¼).

import math
import random


def pollard_rho(n: int) -> int:
    """Возвращает нетривиальный делитель составного n."""
    if n % 2 == 0:
        return 2

    while True:
        x = random.randrange(2, n)
        y = x
        c = random.randrange(1, n)
        d = 1

        while d == 1:
            x = (x * x + c) % n
            y = (y * y + c) % n
            y = (y * y + c) % n      # y движется вдвое быстрее
            d = math.gcd(abs(x - y), n)

        if d != n:
            return d                  # нашли делитель
        # иначе пробуем другие x и c

Алгоритм построен на «парадоксе дней рождения»: среди случайных остатков быстро находится пара, разность которой имеет общий делитель с n. Схема с двумя указателями (x и y, движущимся вдвое быстрее) — это поиск цикла Флойда, отсюда и название «ро» — траектория напоминает греческую букву ρ.

На практике перед Поллардом проверяют число на простоту тестом Миллера-Рабина, иначе алгоритм зациклится.

Что даёт разложение

Многие функции считаются прямо из разложения по формулам.

Количество делителей. Если n = p₁^a₁ · p₂^a₂ · … · pₖ^aₖ, то число делителей равно произведению (aᵢ + 1):

def count_divisors(n: int) -> int:
    result = 1
    for power in factorize(n).values():
        result *= power + 1
    return result


print(count_divisors(360))   # 24

Логика: каждый простой множитель можно взять в степени от 0 до aᵢ, то есть aᵢ + 1 способами, и выборы независимы.

Сумма делителей — произведение геометрических прогрессий:

def sum_divisors(n: int) -> int:
    result = 1
    for p, a in factorize(n).items():
        result *= (p ** (a + 1) - 1) // (p - 1)
    return result


print(sum_divisors(360))   # 1170

Функция Эйлера — количество чисел от 1 до n, взаимно простых с n:

def euler_phi(n: int) -> int:
    result = n
    for p in factorize(n):
        result = result // p * (p - 1)
    return result


print(euler_phi(360))   # 96
print(euler_phi(97))    # 96 — для простого это p-1

Функция Эйлера нужна для теоремы Эйлера, обобщающей малую теорему Ферма на составные модули.

НОД и НОК через разложение. НОД — минимальные степени общих простых, НОК — максимальные. На практике для НОД проще алгоритм Евклида, но понимание через разложение объясняет, почему НОД(a,b) · НОК(a,b) = a · b.

Практическое применение

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

Сокращение дробей — деление числителя и знаменателя на НОД.

Задачи на делимость в олимпиадном программировании.

Проверка простоты. Если разложение состоит из одного множителя в первой степени — число простое.

Частые ошибки

Забытый остаток в конце. Пропуск if n > 1 теряет наибольший простой множитель. Проверьте на числе 14 или любом полупростом.

Использование sqrt(n) вместо d * d <= n. Ошибки округления могут «съесть» последний делитель у чисел, близких к полному квадрату.

Перебор всех чисел вместо нечётных. Работает, но вдвое медленнее. Обработка двойки отдельно позволяет дальше идти с шагом 2.

Пересчёт sqrt(n) внутри цикла. Значение n уменьшается при делении, поэтому граница должна проверяться заново — условие d * d <= n делает это автоматически.

Ро-метод на простом числе. Зациклится. Сначала тест на простоту.

Что запомнить

• Разложение на простые единственно — это основная теорема арифметики.
• Перебор до √n достаточен: больший делитель всегда идёт в паре с меньшим.
• Обязательно обрабатывайте остаток после цикла — это простое больше корня.
• Для массовой факторизации стройте решето минимальных делителей: O(log n) на запрос.
• Из разложения напрямую считаются количество и сумма делителей, функция Эйлера.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→