Задача о минимальном числе, составленном из множителей разбиения

На днях наткнулся на небольшую, но интересную задачку. Условие звучит так:
Задано целое десятичное число N такое, что 9 < N < 10^5. Требуется найти такое минимальное положительное десятичное целое число, произведение цифр которого равно числу N. Если такое число найти не удается, требуется вернуть 0.

Например, задано число 20. Его можно разбить на множители несколькими способами, которые подходят под условие задачи (исключаем множители 10 и 20, так как они не являются цифрами, плюс исключаем единицу, так как в данном случае она будет лишь способствовать увеличению числа-результата за счет дополнительного разряда):
1. цифры 4 и 5
2. цифры 2, 2 и 5
Из найденных цифр можно составить несколько чисел. Решением будет число 45, так как оно будет наименьшим среди всех возможных вариантов.

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

Итак, вот примерный алгоритм. Допустим, у нас на входе задано число N. Определим некий аккумулятор, в который будем накапливать цифры для найденного решения. Для того, чтобы получить минимальное кол-во множителей разбиения, будем делить наше входное число на числа от 9 до 2 (именно в таком порядке). В этом случае, если у нас число N делится на 2 и на 3, например, то сначала мы найдем число 6, и, таким образом, сократим итоговую последовательность цифр.
Если после деления на очередной делитель мы получим остаток от деления 0, то добавляем этот делитель в голову нашего аккумулятора. Таким образом, при добавлении каждого очередного множителя, на которое разбивается наше число, цифры аккумулятора будут сдвигаться вправо, а слева всегда будет добавляться меньшее значение. То есть, в аккумляторе мы всегда получим набор цифр, отсортированный по возрастанию, что нам и нужно.
Так вот, если остаток от деления на очередной делитель получается равным 0, мы добавляем делитель в аккумулятор и проверяем, не равно ли полученное частное единице. Если равно, мы дошли до конца нашего числа, и можем смело вернуть значение аккумулятора, как результат выполнения функции.
Если же нет, то снова начинаем цикл деления на множители от 9 до 2, но уже на вход подаем частное от целочисленного деления N / i (где i - это наш тестируемый делитель).
А если получилось так, что мы прошли по всем числам от 9 до 2 и ни на одно из них наше число не делится без остатка, то мы имеем дело с числом, которое не получится разложить на множители, представляемые десятичными цифрами. В этом случае возвращаем 0, как указано в условии задачи.
Вот несколько облагороженное решение, реализующее данный алгоритм на языке PHP:
===================

<?php

function solver($N)
{
    $acc = '';
    for (;;) {
        for ($i = 9; $i >=2; --$i) {
            if ($N % $i === 0) {
                break;
            }
        }
        if ($i > 1) { // если вышли по break
            $acc = $i . $acc;
            $N = (int)floor($N / $i);
            if ($N === 1) {
                return (int)$acc;
            }
            continue;
        } else { // нет делителей от 2 до 9 включительно
            return 0;
        }
    }
}

echo "20 => " . solver(20) . "\n"; // выводит '45'

echo "1000 => " . solver(1000) . "\n"; // выводит '5558'

echo "34 => " . solver(34) . "\n"; // выводит '0'

=================
Вот такая любопытная задачка ) Надеюсь, вам было тоже интересно )