We try to decompose the problem in form of a tree, starting from the input number that can be branched in 29 ways (as the branch with value 1 means the input number itself). Our goal is to find the shortest path from the root to the leaf, while generating the minimal number. We try branching from the highest number first, as then we will construct the shortest path.
48
/\
8 6 4.. 2
/  \
6 8 6

2
Also assuming that if a number is divisible by 8, then no need to divide further by 4 and 2 (factors) and this is done by maintaining information about all the previous numbers seen, using a seen variable.
public int smallestFactorization(int a) {
if (a <= 1) return a;
long ans = Long.MAX_VALUE;
int seen = 1;
for (int idx = 9; idx > 1; idx )
if (seen % idx != 0 && a % idx == 0) {
seen *= idx;
int val = smallestFactorization (a/idx);
if (val > 0) ans = Math.min (ans, val == 1 ? idx : 10l * val + idx);
}
return (ans == Long.MAX_VALUE  ans > Integer.MAX_VALUE) ? 0 : (int) ans;
}