[算法] 分解质因数

也不知道这个算不算算法，但是确实有使用价值。

举例：
把一个整数分解为几个因数相乘的形式，如，19000=2*2*2*5*5*5*19。

一看很简单，但是真的敲键盘的时候就会考虑很久。

实现源码：

private String coreMethod(int num) {//输入要分解的数
int k = 2;//设定初始因数
StringBuilder sb = new StringBuilder(num+"=");//结果
while(k<=num){
if(k == num){//如果传入的参数为2，也就是最小质因数，那么可以直接返回即可
sb.append(k);
break;
}else if(num % k == 0){//判断k是否为num的因数
sb.append(k+"*");
num = num/k;//懂的
}else
k++;
}
return sb.toString();
}

测试：

这个也是个很巧妙的算法。

突然想到一个在大一的时候就做过的问题，现在用这个感觉会简单到不行了。

就是一个找零的问题，大概是这样描述的：

一张面值随意的人民币，在付款后找零该如何操作。（其实应该还有一些什么使用张数最少之类的限制，不讨论了）

此处相当于用已有面值来凑需要找零的面额。

那么就是把上述代码中的k值限定，k值取指定的数据即可，如k={2，5，10，20}.

代码：

private String coreMethod(int num) {
int k = 0;
int [] data = {100,50,20,10,5,2,1};
StringBuilder sb = new StringBuilder(num+"=");
while(0<=num){
if(0 >= num){
break;
}else if(num >= data[k]){
sb.append(data[k]);
num = num-data[k];
if(num != 0)
sb.append("+");
}else
k++;
}
return sb.toString();
}

算法和以上分解的思路是一样的，结果：