Задача про Произведение цифр

[newStudent]

Доброго времени суток! Есть следующая задача:

Задача
Найти минимальное положительное целое число Q такое, что произведение цифр числа Q в точности равняется N.

Исходные данные
Целое число N (0 ≤ N ≤ 10^9).

Результат
Выведите целое число Q. Если такого числа не существует, выведите −1.

Пример
Исходные данные: 10
Результат: 25

Вопрос: какой алгоритм можете посоветовать для решения этой задачи?
Заранее спасибо!

P.S. Нужно понять саму суть алгоритма. С реализацией его на ЯП, думаю, справлюсь сам.

[Serge_Bliznykov]

Нужно понять саму суть алгоритма. С реализацией его на ЯП, думаю, справлюсь сам.

извините, но для проверки своей идеи набросал пример кода.
вроде бы работает.
идея в том, чтобы формировать число как результат деления на возможные цифры, начиная от больших к меньшим (от 9 до 2):

function IntToStr(L : longInt) : string;
var s : string;
begin
  str(L, s);
  IntToStr := s;
end;

var N :  longint;
   chislo : string;
   i, D1 : integer;
begin
  Readln(N);

  chislo := '';

    for D1 := 9 downto 2 do begin
      while (N>1) and ((N mod D1) = 0) do begin
         chislo :=  IntToStr(D1) + chislo;
         N := N div D1;
      end;
    end;

  if N=1 then WriteLn('Число найдено. Это '+ chislo)
  else  WriteLn('Не удалось подобрать число');

  readln;

end.

[Д_М]

1) Выделить из N максимальные степени 2, 3, 5, 7:

N = 2^n1 * 3^n2 * 5^n3 * 7^n4 * x

2) if(x != 1) return -1;

3) Из двух двоек можно сделать 4, из 3-х двоек - 8, из 2-х троек - 9, из 2 и 3 - шестерку.
Надо как-то минимизировать кол-во цифр.

Получаем разложение N=2^m1 * 3^m2 * 4^m3 * 5^....
(причем m1 и m2 либо 0 либо 1)

4) for(i=0; i<m1;++i) cout << '2'
for(i=0; i<m2;++i) cout << '3'
и т.д.

Кажется так. Осталось додумать п.3

[veniside]

1) если N < 10, то Q = "1" + N

2) иначе, запускаем вот такое:

function tryQ(N, q: integer; const s: string): string;
var
  i: integer;
begin
  result := '';
  //
  for i := 9 downto 2 do begin
    //
    if (9 * q < N) then begin
      //
      result := tryQ(N, i * q, s + IntToStr(i));   // no reason to try now, N is too big
      if ('' <> result) then
        break;
    end
    else begin
      //
      if (i * q = N) then begin
        //
        result := s + IntToStr(i);
        break;
      end;
    end;
  end;
end;

var
  s: string;
begin
  s := tryQ(10, 1, '');  // N = 10
  // ...

3) в полученном s сортируем цифры по возрастанию.

Вроде всё.

PS. Serge_Bliznykov, ого, чё-то я перемудрил ) ладно, пусть будет и вариант с рекурсией )

[Д_М]

PS. Serge_Bliznykov, ого, чё-то я перемудрил

Мне тож какие-то ужасы померещились. Оказывается, все не просто, а очень просто

[newStudent]

Всем спасибо за подробное объяснение. Тяжело не разобраться ))
P.S. Тему можно закрывать.