572. Урок математики

В начале каждого урока учительница математики Гузель Закиевна пишет на доске натуральное число n. Пока идет урок, школьники стараются найти как можно больше простых делителей этого числа. В конце урока щедрая Гузель Закиевна награждает конфеткой всех, кто нашел максимальное количество простых делителей.

Школьник Вася очень любит сладкое и просит вас помочь ему получить конфетку от Гузель Закиевны. Для заданного числа n выведите все его простые делители и степени, в которых они встречаются в числе.

Вход. Одно натуральное число n (n ≤ 10⁹).

Выход. Выведите все простые делители числа n в порядке возрастания. Для каждого делителя укажите степень, в которой он встречается в числе n, если эта степень больше единицы. Формат вывода должен соответствовать примеру.

Пример входа	Пример выхода
3240	2^3*3^4*5

РЕШЕНИЕ

разложение на множители

Анализ алгоритма

В задаче необходимо разложить на множители число n. Для этого переберем все его возможные простые делители от 2 до . Для каждого делителя подсчитаем, сколько раз он входит в n.

Реализация алгоритма

Функция factor выполняет разложение числа n на простые множители.

void factor(int n)

{

for (int i = 2; i <= sqrt(n); i++)

{

if (n % i) continue;

Число i является делителем n. В переменной c подсчитаем степень, с которой оно входит в разложение n.

int c = 0;

while (n % i == 0) n /= i, c++;

Выводим множитель i^c. Если степень множителя c = 1, выводим только i. В противном случае выводим множитель i с его степенью.

if (c > 1) printf("%d^%d",i,c); else printf("%d",i);

Если число n еще не разложено полностью (n > 1), выводим знак умножения.

if (n > 1) printf("*");

}

Если после завершения цикла значение n больше 1, то оно является простым.

if (n > 1) printf("%d",n);

printf("\n");

}

Основная часть программы. Читаем входное число n и запускаем его факторизацию.

scanf("%d",&n);

factor(n);

Python реализация

import math

Функция factor выполняет разложение числа n на простые множители.

def factor(n):

for i in range(2, math.isqrt(n) + 1):

if n % i: continue

Число i является делителем n. В переменной c подсчитаем степень, с которой оно входит в разложение n.

c = 0

while n % i == 0:

n //= i

c += 1

Выводим множитель i^c. Если степень множителя c = 1, выводим только i. В противном случае выводим множитель i с его степенью.

if c > 1: print(i,"^",c, sep = "", end="")

else: print(i, end="")

Если число n еще не разложено полностью (n > 1), выводим знак умножения.

if n > 1: print("*", end="")

Если после завершения цикла значение n больше 1, то оно является простым.

if n > 1: print(n)

else: print()

Основная часть программы. Читаем входное число n и запускаем его факторизацию.

n = int(input())

factor(n)