842. Разложение
на простые множители
Вывести представление целого
числа n в виде произведения простых чисел.
Вход. Одно число n (2 ≤
n ≤ 231 – 1).
Выход. Вывести список простых множителей
в порядке неубывания, разделённых знаком “*”.
|
Пример
входа 1 |
Пример выхода
1 |
|
30 |
2*3*5 |
|
|
|
|
Пример
входа 2 |
Пример выхода
2 |
|
16 |
2*2*2*2 |
РЕШЕНИЕ
разложение на множители
Анализ алгоритма
В задаче
необходимо разложить на множители число n.
Для этого переберем все его возможные простые делители от 2 до 
и выведем каждый
делитель столько раз, сколько раз он входит в факторизацию числа n.
Реализация алгоритма
Функция factor раскладывает число n на множители. Факторизацию
выводим в формате, заданном в условии задачи.
void factor(int n)
{
for (int i = 2;
i <= sqrt(n); i++)
{
Число i является делителем n. Выводим число i столько
раз, сколько оно входит в разложение числа n.
while (n % i ==
0)
{
printf("%d", i);
n /= i;
if (n >
1) printf("*");
}
}
Если после окончания цикла значение n больше 1, то оно простое и его
следует вывести.
if (n >
1) printf("%d", n);
printf("\n");
}
Основная часть программы. Читаем входное значение n и выводим его разложение на множители.
scanf("%d", &n);
factor(n);