题目描述
现给定任意正整数 n，请寻找并输出最小的正整数 m（m>9），使得 m 的各位（个位、十位、百位 ... ...）之乘积等于n，若不存在则输出 -1。
我的题解
暴力法
最原始的想法是遍历，由于这个数一定不小于n，于是从n开始累加，然后转化为字符数组，计算积，判断
这个方法很傻，而且很难设置终止条件。
public int solution (int n) {
int a = n;
while(true){
char [] arr = Integer.toString(a).toCharArray();
int m=1;
for(char s:arr){
m*=s-48;
}
if(m>6*n)return -1;
else if (m==n) return a;
a++;
}
}
因式分解法
先把这个数彻底因式分解 n=n1*n2···nx
如果有个因子大于9，一定不存在m，why？
我们知道这个因子一定不是2-9的倍数，那么我们用个位数的乘积一定得不到这个数，故一定不存在m，直接返回-1
于是我们确定因式分解后因子 在2~9之间
我们使用数组来存放每个因子出现的次数。arr[i]代表i出现的次数
要使m最小，那么一定要使大的数字在低位，如9应该放在个位等低位。
我们从高位9到低位2扫描数组，找出所有的能够组成较大的数的因子，用于填充低位。
最后得到的数一定是最小的。
public int solution (int n) {
int arr[] = new int[10]; //2~9用于存放因子个数
for(int i=2;;i++){//因式分解,从2~9判断
if(n==1)break;//完成
if(i>9)return -1;//有大于9的因子，返回-1，结束
if(n%i==0){ // 可以整除
arr[i]++;//因子数量+1
n = n/i; //除去因子
i--; //彻底分解，再次判断还能不能被i分解
}
}
String res = ""; //用一个字符串存放结果
for(int i=9;i>0;i--){ //从高位（9）开始扫描
while(arr[i]>0){ //先看是否存在单个这样的数，如9
res=i+res;
arr[i]--;
}
//再看有没有多个数积是i的
//由于不同的i 的因子组成不同，如8=2*2*2= 2*4,于是分情况讨论
switch(i){
case 9:
while(arr[3]>=2){
res="9"+res;
arr[3]-=2;
}
break;
case 8:
while(arr[2]>=3){
res="8"+res;
arr[2]-=3;
}
while(arr[2]>0&&arr[4]>0){
res="8"+res;
arr[2]--;
arr[4]--;
}
break;
case 6:
while(arr[2]>0&&arr[3]>0){
res="6"+res;
arr[2]--;
arr[3]--;
}
break;
case 4:
while(arr[2]>=2){
res="4"+res;
arr[2]-=2;
}
//7、5、3是素数，不能被非1因子分解
}
}
return Integer.valueOf(res);//返回结果
}