[Тестовое СБЕР] Разложение на простые множители

Эта задача с собеседования на позицию Junior Data Engineer & Data Science в СБЕР

Дано

Дано число n. Необходимо разложить факториал этого число на простые множители и представить результат в строковом виде.

Задание

Напишите функцию decomp, которая будет возвращать строку вида a^b * c^d * ... * e.

Примечание: Простые числа должны быть в порядке возрастания.

Примечание: Когда показатель простого числа равен 1, не ставьте показатель степени.

Функция decomp принимает на вход только число n.

Важно: Лишних пробелов быть не должно. Но вокруг знаков умножения должны быть пробелы.

Пример:

n = 12
Ответ: 2^10 * 3^5 * 5^2 * 7 * 11

Пример:

n = 22
Ответ: 2^19 * 3^9 * 5^4 * 7^3 * 11^2 * 13 * 17 * 19

Дополнительная информация

Обратите внимание, что шаблон решения представлен в виде (на примере языка Python):

class Answer:
    def function(self, arg1, arg2):
        # напишите свой код ниже

        return res

Здесь function - функция, которую вам нужно написать (от задачи к задаче ее имя меняется), а arg1, arg2 - аргументы этой функции.

Чтобы решить задачу, напишите свой код между комментарием и выражением return ....

Если вы хотите промежуточно посмотреть, что вернет написанный вами код, воспользуйтесь конструкцией и нажмите кнопку Выполнить:

print(Answer().function(arg1, arg2))

Если вам нужно импортировать какой-то модуль, указывайте модуль до class Answer. Например:

import mymodule 

class Answer:
    ...

Полный пример:

# импортируем модуль
import collections

class Answer:
    def problemSolve(self, n, m):
        # напишите свой код ниже
        ...
        return res

# промежуточно смотрим результат
print(Answer().problemSolve(n=2, m=3))