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

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

Формат ввода

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

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

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

Пример

Ввод

120

Вывод

2 * 2 * 2 * 3 * 5

Ввод

98

Вывод

2 * 7 * 7

Решение

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

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

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

Посмотреть код

Решение

Python
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

Решение

Python
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
Подписаться
Уведомить о
guest
4 комментариев
Старые
Новые Популярные
Межтекстовые Отзывы
Посмотреть все комментарии
lava
lava
08.02.2024 09:52

Одна проблема – в этом параграфе еще не подразумеваются вложенные циклы…

Макс
Макс
15.04.2024 17:33

if not number % divider не пойму какая логика в этом выражении проверяется?

Последний раз редактировалось 7 месяцев назад Макс ем