Łatwiejszy sposób na rozwiązanie zadania

Hej! Mam zadanko, najmniejszy problem jest z kodem, a największy z pomysłem. Otóż: "Adam wymyślił nową zagadkę.
Polega ona na znalezieniu najmniejszej liczby , której iloczyn cyfr jest równy N". Napisałam taki najprostszy sposób:

 
#include <iostream>
#include <string.h>
using namespace std;
int ilo(string x)
{
    int h=1;
    for (int i=0; i<x.size(); i++)
    {
        h=h*(x[i]-'0');
    }
    return h;
}
int intToStr(int n)
{
    string tmp, ret;
    if(n < 0) {
        ret = "-";
        n = -n;
    }
    do {
        tmp += n % 10 + 48;
        n -= n % 10;
    }
    while(n /= 10);
    {
        for(int i=tmp.size()-1; i>=0; i--)
            ret += tmp[i];
    }
    return ilo(tmp);
}
int main()
{
    int x;
    cin>>x;
    for (int i=1; i<=1000000005; i++)
    {
        if (intToStr(i)==x)
        {
            cout<<i<<endl;
            return 0;
        }
    }
    
    return 0;
}                

Problem jest z limitami czasu :/
Pomoże ktoś? Jakiś pomysł? Dzięki :)

Niech a to liczba która jest podana, a b to liczba, której iloczyn cyfr daje a.
b = 0
Dopóki a != 1
c = Znajdź dzielnik liczby a w zakresie <2,9> (jeśli nie ma to zadania nie da się wykonać, chyba że a to 1 lub 0)
jeśli nie ma to wyjdź z pętli
a/=c
dodaj do liczby a cyfrę c (tak jak konkatenuje się stringi)
jeśli b==0 to b=a

Dzięki, zrozumiałam :D Idę zakodzić, jak będę miała problemy to napiszę.

Napisałam:

 
#include <iostream>
using namespace std;
string fnkc(int x)
{
    int a=0;
    string b;
    while (a!=1)
    {
        for (int i=2; i<=9; i++)
        {
            if (x%i==0)
            {
                a=i;
                x=x/a;
                b+=a+'0';
            }
            else
            {
                if (i==9)
                {
                    a=1;
                }
            }
        }
    }
    return b;
}
int main()
{
    int a;
    cin>>a;
    cout<<fnkc(a)<<endl;
}

Ale przy wpisaniu 28 wypisuje 27....

Skoro idziemy w stringi, to szkoda sprawdzać wszystko co ma jedynkę na początku lub też zero na końcu, bez nich wyjdzie mniejsza liczba z tym samym iloczynem. Przy dwucyfrowych iloczynach, nie ma co sprawdzać liczb poniżej 25, zaś przy jednocyfrowym iloczyn będzie wynikiem. Podejrzewam zresztą że najlepiej było iść nie w sprawdzanie kolejnych liczb, tylko dzielników liczby końcowej i ich ew wielocyfrowych wyników. np wspomniane 28 / 4 = 7, zatem najmniejszy wynik z takim iloczynem to 47. 3-cyfrowe wyniki zaczną się od 82 (bo 9 * 9 == 81), od takiego wyniku musisz sprawdzać "wyniki cząstkowe" z dzielenia oryginalnego wyniku.

a to nie będzie czasem coś w ten deseń?
http://ideone.com/1u3BSt

złożoność logarytmiczna, jakby trochę dodawanie stringów zoptymalizować.

EDIT: dobra nie zadziała to dla przypadków typu: 12. Wynik powinien być 26 a mój prog by zwrócił 34. Podejrzewam, że jakby ten mój program zmodyfikować trochę, żeby brut forcem dzielników szukał to bybybłby mimo wszystko szybszy Działa dla tego akurat, ale nie jestem przekonany do poprawności mimo wszystko

Ja wpuściłam to:

#include <iostream>
#include <algorithm>
using namespace std;
int ilo(string x)
{
    int h=1;
    for (int i=0; i<x.size(); i++)
    {
        h=h*(x[i]-'0');
    }
    return h;
}int main()
{
    int x;
    cin>>x;
    int a=0;
    string b;
    while (a!=1)
    {
        for (int i=9; i>=2; i--)
        {
            if (x%i==0)
            {
                a=i;
                x=x/a;
                b+=a+'0';
             }
            else
            {
                if (i==9)
                {
                    a=1;
                }
            }
        }
    }
    sort(b.begin(), b.end());
    cout<<b<<endl;
    return 0;
} 

Ale weszło na 30 pkt, czyli jeszcze mniej....

Zaczynasz od warunku, jeżeli liczba<=9 to wyświetlasz liczbę i na tym koniec.
W przeciwnym przypadku, rozkładasz na liczby pierwsze: 2 3 5 7
Po czym zamieniasz: wszystkie 222 na 8, wszystkie 33 na 9, wszystkie 32 na 6, wszystkie 2*2 na 4, wypisujesz od najmniejszej do największej.
Czyli coś na kształt:

int main()
  {
   unsigned n,cnt;
   scanf("%u",&n);
   if(n<10) printf("%u",n);
   else
      {
       unsigned digits[10]={0};
       while(!(n%7)) { ++digits[7]; n/=7; }
       while(!(n%5)) { ++digits[5]; n/=5; }
       while(!(n%3)) { ++digits[3]; n/=3; }
       while(!(n%2)) { ++digits[2]; n/=2; }
       cnt=digits[2]/3; digits[2]-=3*cnt; digits[8]=cnt;
       cnt=digits[3]/2; digits[3]-=2*cnt; digits[9]=cnt;
       cnt=min(digits[2],digits[3]); digits[2]-=cnt; digits[3]-=cnt; digits[6]=cnt;
       cnt=digits[2]/2; digits[2]-=2*cnt; digits[4]=cnt;
       for(unsigned i=1;i<=9;++i) for(unsigned cnt=digits[i];cnt>0;--cnt) printf("%u",i);
       printf("\n");
      }
   return 0;
  }

Po zastanowieniu się, można i tak:

int main()
  {
   unsigned n;
   scanf("%u",&n);
   if(n<10) printf("%u",n);
   else
      {
       unsigned digits[10]={0};
       for(unsigned i=9;i>=2;--i) for(;!(n%i);n/=i) ++digits[i];
       for(unsigned i=2;i<=9;++i) for(unsigned k=digits[i];k>0;--k) printf("%u",i);
       printf("\n");
      }
   return 0;
  }

@ZosiaZamoyska

źle popatrzyłem

po znalezieniu prawidłowej cyfry powinnaś wyjść z pętli

w dodatku pętla powinna iść od 2 do 9 a nie na odwrót i na końcu nie musisz sortować tego stringa.

@Sopelek ale to zmienną x podaje użytkownik.