R. Простая задача 2.0

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

Формат ввода

Вводится одно натуральное число.

Формат вывода:

Требуется составить математическое выражение — произведение простых неубывающих чисел, которое в результате даёт исходное.

Пример

Ввод

120

Вывод

2 * 2 * 2 * 3 * 5

Ввод

98

Вывод

2 * 7 * 7

Решение

Алгоритм достаточно простой: Если число равно единице, печатаем единицу и прекращаем выполнение. В противном случае, инициализируем делитель единицей. Пока число больше единицы увеличиваем делитель на единицу (в первой итерации он становится равным двум) и проверяем делится ли нацело наше число не делитель. Если делится, то выводим делитель и проверяем равен ли делитель числу. Если нет, выводим знак умножения. По окончании всех проверок делим число на делитель и инициализируем делитель единицей.

Второй способ решения предполагает вложенные циклы (следующая тема). Если число равно единице, печатаем единицу и прекращаем выполнение. В противном случае, находим первый простой делитель, на который делится число и делим число до тех пор, пока оно делится без остатка. Как только операция стала невозможна, находим следующий делитель. Продолжаем до тех пор, пока результат деления не станет меньшим или равным чем два.

Алгоритм поиска простого числа можно взять из задачи N. Простая задача

number = int(input())
divisor = 1

if number < 2:
    print(number)
while number > 1:
    divisor += 1
    if not number % divisor:
        print(divisor, end='')
        if number != divisor:
            print(' *', end=' ')
        number //= divisor
        divisor = 1

number = int(input())

if number == 1:
    print(number)

divisor = 2

while number >= 2:
    prime = True

    while divisor ** 2 <= number and prime is True:
        if number % divisor == 0:
            prime = False
        else:
            divisor = divisor + 1
    if prime is True:
        print(number)
        number = 1
    else:
        print(f'{divisor}', end=' * ')
        number = number // divisor