1) с начала строки по одному символу отщипываешь, пока не получится последовательность, соответствующая букве.
2) Запоминаешь получившуюся букву, и для оставшейся строки делаешь то же самое.
3) Если для остаток строки получилось разложить на символы, то добавляешь свою букву и возвращаешь результат.
Иначе повторяешь пункт 1 пока не получится новый символ. И потом снова пункт 2 и 3.
Если строка кончилась, а буква не получилась (тут можно обрезать по длине последовательности), то сообщаешь вызвавшему коду об ошибке.
В итоге у тебя получится разложение, но оно может быть не единственным, но я думаю это ты сам модифицируешь алгоритм.
yuharu: так я и написал как. Не перебирать все числа, а сначала понять, какое должно быть разложение на простые числа (факторизация). А потом просто взять первые несколько простых чисел - тогда будет минимальное число.
Твоё искомое число представляется в a * a * ... * a * b * b * .. * b * c ..
где a, b, c - это различные простые числа.
Например
2 * 2 * 3 * 5 * 5
a a b c c
Данное разложение можно разделить пополам несколькими различными способами
| aabcc
a | aabcc
aa | bcc
ab | abcc
...
и т.д.
Число таких вариантов разделения - это твоё k
Тебе надо найти такие последовательности aabbc, которые дают тебе именно заданное число разделений.
После этого, как у тебя появилось несколько претендентов на разделение
например aabbc и abcd
ты вместо букв подставляешь первые несколько простых чисел - и смотришь какой вариант даст минимальное число.
Чем больше раз буква встречается - тем меньшее простое число должно ей соответствовать.
Но всё равно может быть придётся проверить несколько вариантов.
Попробуй пройти бесплатные курсы по питону, например на https://stepik.org/catalog?q=python
есть неплохие.