Разложение на простые множители Вывести представление целого числа N в виде произведения простых чисел.
Входные данные
В первой строке находится единственное число N. 2 <= N <= 231 - 1.
Выходные данные
Выводится список чисел в порядке неубывания, разделённых знаком "*".
Примеры
входные данные
30
выходные данные
2*3*5
входные данные
16
выходные данные
2*2*2*2
на Python
n = int(input())
dx = []
k = 2
while k <= n ** 0.5:
if n % k == 0:
dx.append(k)
n = n // k
else:
k += 1
if n > 1:
dx.append(n)
print('*'.join(str(s) for s in dx))
Объяснение:
Для начала проверим, можно ли число N разделить на самое маленькое простое число - 2. Если число N делится на 2 без остатка, то мы делим его на 2 и записываем его в разложение. Повторяем этот шаг до тех пор, пока число N не будет делиться на 2 без остатка. Таким образом, мы найдем все степени числа 2 в разложении.
Далее проверим, можно ли число N разделить на простое число - 3. Если число N делится на 3 без остатка, то мы делим его на 3 и записываем его в разложение. Повторяем этот шаг до тех пор, пока число N не будет делиться на 3 без остатка. Таким образом, мы найдем все степени числа 3 в разложении.
Продолжаем этот процесс с простыми числами, начиная с 2 и заканчивая квадратным корнем числа N. Если после этого число N останется больше 1, то оно само является простым числом и записывается в разложение.
Вот подробное пошаговое решение для числа N = 30:
1. N = 30 делится на 2 без остатка, значит, добавляем 2 в разложение.
2. Теперь N = 15 (30 / 2).
3. N = 15 не делится на 2 без остатка, переходим к следующему простому числу - 3.
4. N = 15 делится на 3 без остатка, значит, добавляем 3 в разложение.
5. Теперь N = 5 (15 / 3).
6. N = 5 не делится ни на 2, ни на 3. Поскольку 5 - простое число, добавляем его в разложение.
7. Завершаем разложение, так как число N стало равным 1.
Результат разложения числа 30 на простые множители: 2 * 3 * 5.
Аналогично решим задачу для числа N = 16:
1. N = 16 делится на 2 без остатка, значит, добавляем 2 в разложение.
2. Теперь N = 8 (16 / 2).
3. N = 8 делится на 2 без остатка, значит, добавляем 2 в разложение.
4. Теперь N = 4 (8 / 2).
5. N = 4 делится на 2 без остатка, значит, добавляем 2 в разложение.
6. Теперь N = 2 (4 / 2).
7. N = 2 не делится ни на 2, ни на 3. Поскольку 2 - простое число, добавляем его в разложение.
8. Завершаем разложение, так как число N стало равным 1.
Результат разложения числа 16 на простые множители: 2 * 2 * 2 * 2.
Таким образом, получаем ответ на задачу.