Find the smallest number Q whose product of digits is N How do I make this efficient?

#include &lt;stdio.h&gt;
#define MAX 1000000000

int main()
{
    int n,temp,prod,i,j=0;
    scanf("%d",&amp;n);

    for(i=1;i&lt;MAX;i++)
    {
        temp=i;
        prod=1;
        while(temp!=0)
        {
           prod=prod*(temp%10);
           temp=temp/10;
        }
        if(prod==n)
        {
            printf("%d",i);
            j=1;
            break;
        }

    }
    if(j==0)
    {
        printf("-1");
    }
    return 0;
}
An efficient solution would be to express n as its prime
  factorization \$2^a3^b5^c7^d\$. Then, try to regroup those factors into the
  fewest number of 2, 3, 4, 5, 6, 7, 8 digits possible, in increasing
  order. If n has a prime factor larger than 7, then there is no
  solution.


The right way to group the \$2^a3^b\$ factors in 2,3,6,8,9 digits is first to minimize the number of digits, giving priority to \$2^3\$. You then end up with \$3^b\$ or \$2^13^b\$ or \$2^23^b\$. For \$b&gt;2\$ you group by \$3^2\$. I then solved all the solutions for \$2^a3^b\$ with \$a,b\leq2\$ and figured out that the following precedence works : (9,8,7,6,5,4,3,2). So there must be a more elegant proof!

Note that the solution will have at most one 2 or one 3 or one 4.

int numberOfFactor(int * n, int factor)
{
    int number_of_factor = 0;
    while (*n % factor == 0)
    {
        *n /= factor;
        number_of_factor++;
    }
    return number_of_factor;
}

int appendDigits(int digit, int n_digit, int initial_shift)
{
    int i;
    int ret = 0;

    for (i=0; i&lt;n_digit; i++)
        ret = ret + digit * pow (10, i + initial_shift);

    return ret;
}

int main()
{
    int n;
    int q;
    int n9, n8, n7, n6, n5;
    scanf("%d", &amp;n);

    if (n &lt;= 9)
    {
        printf("%d", n);
        return 0;
    }

    n9 = numberOfFactor(&amp;n, 9);
    n8 = numberOfFactor(&amp;n, 8);
    n7 = numberOfFactor(&amp;n, 7);
    n6 = numberOfFactor(&amp;n, 6);
    n5 = numberOfFactor(&amp;n, 5);


    if (n&gt;4)
    {
        printf("-1");
        return 1;
    }

    q = appendDigits(9,n9,0) 
      + appendDigits(8,n8,n9)
      + appendDigits(7,n7,n9+n8)
      + appendDigits(6,n6,n9+n8+n7)
      + appendDigits(5,n5,n9+n8+n7+n6)
      + ((n!=1)?appendDigits(n,1,n9+n8+n7+n6+n5):0);

    printf("%d", q);
    return 0;
}


My first post, please be indulgent.