public class Test068
{
/**将一个正整数分解质因数。例如:输入90,打印出90=2*3*3*5。
*
* 思路:
* 1.我们先把质数存放在一个数组内,以为没有办法通过程序获得所有质数,我们这里手动的把部分质数添加进数组。
*
* 2.用正整数对数组内的第一个质数取模,如果结果是0,则表明能整除。
* 90%2=0,表明90能被2整除,90/2=45,那么2就是其中的一个质因数
* 如果结果不是0,则对数组内的第二个质数取模,直至出现结果为0
*
* 3.拿余数对数组内的第一个质数取模,如果结果是0,则表明能整除。
* 45%2 != 0,表明45不能被2整除,2就不是质因数
* 如果结果不是0,则对数组内的第二个质数取模,直至出现结果为0
* 45%3=0,表明45能被3整除,45/3=15,那么3就是其中的一个质因数
*
* 4.继续对余数进行操作,直至余数等于数组内的一个质数,说明该余数不能再被拆分了
*
* 5.通过思路我们可以看出这是个递归动作。
* @param args
*/
public static void main(String[] args)
{
int[] arr = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
StringBuilder sb = new StringBuilder();
int num = 16;
sb = getPrime(num, arr, sb);
System.out.println(num +"="+ sb.deleteCharAt(sb.length()-1).toString());
}
//定义一个函数用来求质因数,num接受一个正整数,arr接受存放质数的数组,sb存放质因数
public static StringBuilder getPrime(int num, int[] arr, StringBuilder sb)
{
for(int x = 0; x < arr.length; x++)
{
//判断正整数对质数取模是否零,如果为零,则执行if语句的代码块
if(num % arr[x] == 0) //当num =1的时候,if语句不成立就会跳出递归
{
//将余数传给getPrime()方法,继续递归。
getPrime(num/arr[x], arr, sb);
//将这个质数存入sb
sb.append(arr[x] + "*");
//找到质数,就不再进行循环判断后面的质数。
break;
}
}
return sb;
}
}
|