Разложение числа на простые множители на Python

Разберем алгоритм разложения числа на простые множители и напишем код на Python.

Разложение числа на простые множители основано на основной теореме арифметики. Она гласит, что любое целое число больше единицы можно представить в виде произведения простых чисел, и притом единственным способом. Этот инструмент является фундаментом школьной математики и криптографии.

Для чего применяется разложение числа на множители:

• Поиск НОД и НОК: Разложение — классический и наглядный способ найти Наибольший общий делитель (НОД) и Наименьшее общее кратное (НОК) для двух и более чисел.
• Приведение дробей к общему знаменателю: Чтобы сложить или вычесть дроби с разными знаменателями, используют НОК, который часто находят через простые множители.
• Сокращение дробей: Зная простые множители числителя и знаменателя, можно легко «зачеркнуть» одинаковые элементы и упростить дробь.
• Извлечение корней: Если нужно извлечь квадратный или кубический корень из большого числа без калькулятора (например, $\sqrt{576}$), разложение на множители позволяет сгруппировать пары одинаковых чисел и легко вынести их из-под знака корня.
• Упрощение степенных выражений: Помогает приводить сложные основания степеней к простым (например, представить $12^{5}$ как ($2^2 \cdot 3)^5 = 2^{10} \cdot 3^5$).
• Поиск всех делителей числа: Разложив число, можно легко определить, на какие еще числа оно делится, и узнать общее количество его делителей.
• Определение типа десятичной дроби: Позволяет узнать, превратится ли несократимая обыкновенная дробь в конечную или бесконечную периодическую десятичную дробь (если в разложении знаменателя есть только двойки и пятерки, дробь будет конечной).

Разложение числа на простые множители (или факторизация) происходит методом последовательного деления. Мы берем исходное число и поочередно делим его на самые маленькие простые числа (2, 3, 5, 7, 11 и так далее), пока в остатке не получится единица.

Пошаговый алгоритм:

1. Запишите число и проведите справа от него вертикальную линию.
2. Найдите самое маленькое простое число (начиная с 2), на которое ваше число делится без остатка. В этом отлично помогают признаки делимости (например, если число четное — оно точно делится на 2; если сумма цифр делится на 3 — то и число делится на 3).
3. Запишите делитель справа от черты, а результат деления — слева под исходным числом.
4. Повторяйте процесс для нового полученного числа. Снова ищите для него минимальный простой делитель.
5. Остановитесь, когда слева у вас останется единица.
6. Запишите ответ: все числа, оказавшиеся справа от черты, перемножаются. Если какие-то множители повторяются, их принято объединять в степени.

Разберем пример: найдем все простые множители числа 120.

120 | 2
 60 | 2
 30 | 2
 15 | 3
  5 | 5
  1 | 

120 | 2
 60 | 2
 30 | 2
 15 | 3
  5 | 5
  1 | 

Результат: $120 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 5$
Или в более компактном виде со степенью: $120 = 2^3 \cdot 3 \cdot 5$

Разберем еще один пример: найдем все простые множители числа 441.

441 | 3
147 | 3
 49 | 7
  7 | 7
  1 | 

441 | 3
147 | 3
 49 | 7
  7 | 7
  1 | 

Результат: $441 = 3 \cdot 3 \cdot 7 \cdot 7$ или $441 = 3^2 \cdot 7^2$

Теперь напишем программу на Python для нахождения простых множителей числа.

Введем целое число, множители которого мы хотим найти.

number = int(input())

number = int(input())

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

factors = []

factors = []

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

while number > 1:

while number > 1:

Внутри цикла while создадим еще один цикл — for со счетчиком, в котором будем подбирать множители числа, начиная с 2 и до самого числа number включительно.

while number > 1:
    for divisor in range(2, number + 1):

while number > 1:
    for divisor in range(2, number + 1):

Счётчик divisor — это текущий делитель числа. Мы будем его наращивать на единицу при каждой итерации цикла. Внутри цикла for будем проверять, делится ли текущее число number на текущий делитель divisor без остатка.

while number > 1:
    for divisor in range(2, number + 1):
        if number % divisor == 0:

while number > 1:
    for divisor in range(2, number + 1):
        if number % divisor == 0:

Если текущее число number делится без остатка на текущий делитель divisor, мы записываем найденный делитель в список factors, сразу же делим наше число на этот делитель и прерываем текущую итерацию цикла с помощью команды break, чтобы начать поиск следующего множителя для уже уменьшенного числа.

while number > 1:
    for divisor in range(2, number + 1):
        if number % divisor == 0:
            factors.append(divisor)
            number //= divisor
            break

while number > 1:
    for divisor in range(2, number + 1):
        if number % divisor == 0:
            factors.append(divisor)
            number //= divisor
            break

В самом конце остается только вывести список полученных делителей числа на экран.

print(factors)

print(factors)

Весь код полностью:

number = int(input())
factors = []

while number > 1:
    for divisor in range(2, number + 1):
        if number % divisor == 0:
            factors.append(divisor)
            number //= divisor
            break

print(factors)

number = int(input())
factors = []

while number > 1:
    for divisor in range(2, number + 1):
        if number % divisor == 0:
            factors.append(divisor)
            number //= divisor
            break

print(factors)

Ввод даных:

>>> 120

>>> 120

Вывод результата:

>>> [2, 2, 2, 3, 5]

>>> [2, 2, 2, 3, 5]