Поиск простой факторизации положительных чисел в Python (итеративно)

Факторизация числа в Python — это разложение целого числа на простые множители: например, 84 = 2 × 2 × 3 × 7. Самый короткий способ — функция factorint из библиотеки SymPy, а вручную задачу решают методом пробных делений с оптимизацией до корня из числа. Ниже — рабочие примеры кода, разбор сложности и готовый мини-проект.

Что такое факторизация и зачем она нужна

Факторизация — это разложение числа на простые множители, которые являются строительными блоками числа. Простые множители числа 12 — это 2 и 3, так как 12 = 2 × 2 × 3. Любое целое число больше 1 раскладывается на простые множители единственным образом (основная теорема арифметики), поэтому результат факторизации не зависит от алгоритма — только от его скорости.

Факторизация лежит в основе криптографии (стойкость RSA опирается на то, что разложить произведение двух больших простых чисел вычислительно тяжело), используется в теории чисел, при сокращении дробей и поиске НОД/НОК.

Простые множители и делители — это не одно и то же

Не путайте две задачи. Простые множители числа 28 — это [2, 2, 7] (с учётом кратности, их произведение даёт 28). Все делители числа 28 — это [1, 2, 4, 7, 14, 28] (любые числа, на которые 28 делится нацело). Дальше мы разбираем именно факторизацию — поиск простых множителей, — а делители вынесли в отдельный пример.

ОНЛАЙН-ПРАКТИКУМ

ЗАПУСК нейросети DEEPSEEK R1 ЛОКАЛЬНО НА СВОЕМ КОМПЬЮТЕРЕ

ЧТО БУДЕТ НА ОБУЧЕНИИ?

• ПОКАЖЕМ, КАК РАЗВЕРНУТЬ МОДЕЛЬ нейросети DEEPSEEK R1 ПРЯМО НА СВОЁМ КОМПЬЮТЕРЕ
• Где и как применять? Потестируем модель после установки на разных задачах
• Как дообучить модель под себя?

Участвовать бесплатно

Итеративный подход: базовый алгоритм

Итеративный метод факторизации заключается в повторном делении числа на его наименьший простой множитель до тех пор, пока результат не станет равным 1. Начинаем с делителя 2 и увеличиваем его, когда деление перестаёт быть нацело.

Пошаговый разбор

1. Создаём пустой список для простых множителей и берём первый делитель — 2.
2. Пока число больше 1, проверяем, делится ли оно на текущий делитель.
3. Если делится — добавляем делитель в список и делим число на него (делитель не меняем, чтобы поймать повторяющиеся множители).
4. Если не делится — увеличиваем делитель на 1.
5. Когда число станет равно 1 — возвращаем список множителей.

Разложим число 84:

def factorize_iteratively(num):
    factors = []
    divisor = 2
    while num > 1:
        if num % divisor == 0:
            factors.append(divisor)
            num //= divisor
        else:
            divisor += 1
    return factors

number = 84
result = factorize_iteratively(number)
print("Простые множители числа", number, ":", result)
# Простые множители числа 84 : [2, 2, 3, 7]

Алгоритм корректен, но у него есть слабое место: для простого числа (например, 1 000 003) делитель будет расти по единице вплоть до самого числа. В худшем случае это O(n) итераций — для больших чисел недопустимо медленно.

Оптимизированный алгоритм: деление до √n

Ключевая оптимизация: если у числа n есть делитель больше √n, то парный к нему делитель меньше √n уже был найден. Значит, перебирать делители достаточно до квадратного корня из числа; если на этом отрезке делителей не нашлось, оставшееся число — простое. Дополнительно отдельно обрабатываем двойку, а затем идём только по нечётным делителям, пропуская заведомо составные чётные.

def prime_factors(n):
    factors = []
    # сначала выносим все двойки
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    # затем только нечётные делители до корня из n
    divisor = 3
    while divisor * divisor <= n:
        while n % divisor == 0:
            factors.append(divisor)
            n //= divisor
        divisor += 2
    # то, что осталось больше 1, — простой множитель
    if n > 1:
        factors.append(n)
    return factors

print(prime_factors(360))   # [2, 2, 2, 3, 3, 5]
print(prime_factors(1000003))  # [1000003]  — простое число, посчитано мгновенно

Условие divisor * divisor <= n вместо divisor <= n ** 0.5 избавляет от работы с числами с плавающей точкой и ошибок округления на больших значениях. Сложность падает до O(√n): число вроде 1 000 003 раскладывается за тысячу с небольшим итераций вместо миллиона.

Все делители числа

Если нужны не простые множители, а полный список делителей, тот же приём с √n собирает делители парами:

def divisors(n):
    result = []
    d = 1
    while d * d <= n:
        if n % d == 0:
            result.append(d)
            if d != n // d:
                result.append(n // d)
        d += 1
    return sorted(result)

print(divisors(28))   # [1, 2, 4, 7, 14, 28]

Факторизация одной строкой: SymPy

В продакшене редко пишут факторизацию руками — для этого есть библиотека SymPy. Функция factorint возвращает словарь, где ключи — простые множители, а значения — их степени.

from sympy import factorint, primefactors

print(factorint(360))     # {2: 3, 3: 2, 5: 1}  -> 360 = 2^3 * 3^2 * 5
print(factorint(2000))    # {2: 4, 5: 3}
print(factorint(65537))   # {65537: 1}  — простое число

# только сами простые множители без степеней
print(primefactors(360))  # [2, 3, 5]

Установка: pip install sympy. Под капотом factorint комбинирует несколько методов — пробные деления для малых множителей, ро-алгоритм Полларда, метод Полларда p−1 и факторизацию на эллиптических кривых (ECM) для больших чисел, — поэтому она справляется с числами, которые наивный перебор не осилит за разумное время. Граничные случаи: factorint(1) возвращает {}, а отрицательное число добавляет в словарь множитель -1: 1.

Сравнение способов

Мини-проект: факторизация по вводу пользователя

Соберём скрипт, который запрашивает положительное целое число и выводит его простые множители оптимизированным методом, с проверкой ввода.

def prime_factors(n):
    factors = []
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    divisor = 3
    while divisor * divisor <= n:
        while n % divisor == 0:
            factors.append(divisor)
            n //= divisor
        divisor += 2
    if n > 1:
        factors.append(n)
    return factors

def main():
    try:
        number = int(input("Введите положительное целое число: "))
        if number <= 0:
            print("Пожалуйста, введите положительное целое число.")
        else:
            result = prime_factors(number)
            print("Простые множители числа", number, ":", result)
    except ValueError:
        print("Неверный ввод. Введите целое положительное число.")

if __name__ == "__main__":
    main()

Частые вопросы

Как разложить число на простые множители в Python?

Самый простой способ — from sympy import factorint; factorint(360), результат {2: 3, 3: 2, 5: 1}. Без сторонних библиотек используйте перебор делителей до √n из примера выше.

Какая сложность у факторизации перебором?

Наивный перебор с шагом +1 — O(n) в худшем случае (на простом числе). Перебор до квадратного корня снижает сложность до O(√n).

Чем простые множители отличаются от делителей?

Простые множители перемножаются обратно в исходное число (28 = 2 × 2 × 7). Делители — это все числа, на которые исходное делится нацело (1, 2, 4, 7, 14, 28).

Почему деление до корня из числа работает?

Делители идут парами a × b = n. Если оба больше √n, их произведение превысит n, что невозможно. Значит, меньший делитель каждой пары всегда не больше √n.

Заключение

Для учёбы достаточно итеративного перебора, но в реальном коде используйте перебор до √n или готовую factorint из SymPy. Понимание того, почему оптимизация до квадратного корня ускоряет алгоритм с O(n) до O(√n), — базовый навык, который пригодится в любой задаче на перебор делителей. Поэкспериментируйте с большими и простыми числами, чтобы прочувствовать разницу в скорости.