Python

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

Разложить число на простые множители — значит представить его как произведение простых чисел. Например, 60 раскладывается так: 2 × 2 × 3 × 5. В Python эту задачу удобно решать циклом: пробуем делить число на маленькие делители и каждый найденный множитель сохраняем в список

Такая задача хорошо тренирует while, остаток от деления %, целочисленное деление // и понимание того, как число постепенно уменьшается

Короткий ответ

def prime_factors(number):
    factors = []
    divisor = 2

    while divisor * divisor <= number:
        while number % divisor == 0:
            factors.append(divisor)
            number //= divisor

        divisor += 1

    if number > 1:
        factors.append(number)

    return factors

print(prime_factors(60))
print(prime_factors(84))
print(prime_factors(97))

Результат

[2, 2, 3, 5]
[2, 2, 3, 7]
[97]

Если число простое, список будет содержать само число

Как работает алгоритм на числе 60

Начинаем с делителя 2. Число 60 делится на 2, значит 2 — первый множитель. Делим 60 на 2, получаем 30. Число 30 снова делится на 2, сохраняем еще одну двойку и получаем 15

15 на 2 уже не делится, поэтому переходим к 3. 15 делится на 3, сохраняем 3 и получаем 5. Дальше остается 5 — это простое число, его тоже добавляем в список

Итог

60 = 2 * 2 * 3 * 5

Почему проверка идет до квадратного корня

В коде есть условие

while divisor * divisor <= number:

Оно означает: нет смысла проверять делители больше квадратного корня из текущего числа. Если у числа есть большой делитель, у него обязательно есть парный маленький делитель, который мы уже успели бы найти

Можно написать проще, но медленнее

while divisor <= number:

Для маленьких учебных чисел это тоже сработает, но хороший вариант сразу показывает нормальную идею оптимизации

Версия для новичков без оптимизации

Если вы только начинаете, можно сначала понять более прямой вариант

def prime_factors_simple(number):
    factors = []
    divisor = 2

    while number > 1:
        if number % divisor == 0:
            factors.append(divisor)
            number //= divisor
        else:
            divisor += 1

    return factors

print(prime_factors_simple(60))

Этот код легче читать: пока число больше 1, пробуем делить. Если делится, сохраняем делитель. Если не делится, пробуем следующий

Как вывести разложение красиво

Список [2, 2, 3, 5] удобен для программы, но человеку приятнее видеть строку

def prime_factors(number):
    factors = []
    divisor = 2

    while divisor * divisor <= number:
        while number % divisor == 0:
            factors.append(divisor)
            number //= divisor
        divisor += 1

    if number > 1:
        factors.append(number)

    return factors

number = 60
factors = prime_factors(number)
text = " * ".join(map(str, factors))

print(f"{number} = {text}")

Результат

60 = 2 * 2 * 3 * 5

Здесь map(str, factors) нужен, потому что join() умеет соединять только строки, а множители у нас хранятся числами

Как обработать 1, 0 и отрицательные числа

Строго говоря, простые множители обычно рассматривают для натуральных чисел больше 1. Поэтому для учебной программы лучше явно проверять входные данные

def prime_factors(number):
    if number < 2:
        return []

    factors = []
    divisor = 2

    while divisor * divisor <= number:
        while number % divisor == 0:
            factors.append(divisor)
            number //= divisor
        divisor += 1

    if number > 1:
        factors.append(number)

    return factors

print(prime_factors(1))
print(prime_factors(0))
print(prime_factors(2))

Если нужно поддержать отрицательные числа, можно отдельно сохранить -1, а потом разложить модуль числа

def prime_factors_with_negative(number):
    if number == 0:
        return []

    factors = []

    if number < 0:
        factors.append(-1)
        number = abs(number)

    divisor = 2
    while divisor * divisor <= number:
        while number % divisor == 0:
            factors.append(divisor)
            number //= divisor
        divisor += 1

    if number > 1:
        factors.append(number)

    return factors

print(prime_factors_with_negative(-60))

Как проверить результат

После разложения можно перемножить найденные множители и проверить, что получилось исходное число

from math import prod

number = 84
factors = prime_factors(number)

print(factors)
print(prod(factors) == number)

Результат

[2, 2, 3, 7]
True

math.prod() перемножает элементы последовательности. Для проверки алгоритма это очень удобно

Мини-практика

Сделайте программу, которая просит число у пользователя и выводит разложение

from math import prod

def prime_factors(number):
    factors = []
    divisor = 2

    while divisor * divisor <= number:
        while number % divisor == 0:
            factors.append(divisor)
            number //= divisor
        divisor += 1

    if number > 1:
        factors.append(number)

    return factors

number = int(input("Введите число: "))
factors = prime_factors(number)

print("Множители:", factors)
print("Проверка:", prod(factors))

Проверьте числа 12, 60, 97 и 100. Так вы увидите разные случаи: повторяющиеся множители, простое число и число с несколькими делителями

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

Первая ошибка — увеличивать делитель после каждого успешного деления. Если число делится на 2 несколько раз, нужно забрать все двойки, а не только одну

Вторая ошибка — забыть добавить остаток number, если после цикла он больше 1. Именно так в разложение попадает последний простой множитель

Третья ошибка — использовать обычное деление /. В этой задаче нужно целочисленное деление //, иначе число станет дробным и проверки начнут вести себя странно

Что почитать дальше по Python

Если нужен общий маршрут по теме, откройте рубрику Python. Для соседних задач пригодятся эти разборы:

0 комментариев

Старые

Новые Популярные