题目：
将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5
代码：
这题目很简单，首先根据输入整数，列出所有小于此整数的素数列表，这些素数都有可能作为被分解整数的因子，然后从最小的素数开始，让被分解的数去除这个数，如果整除，那么此素数就作为因子，然后递归到用分解 原数/当前素数，如果不能整除，那么从候选素数中移除当前的最小素数，挑选下一个素数再尝试，最后所有的因子都被记录在列表中，最后打印出来。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
package
com.charles.algo;
import
java.util.ArrayList;
import
java.util.List;
/**
* @author charles.wang
*
* 题目：将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。
*
*/
public
class
DecompositeToFactor {
// 这个factorList存放了最终被分解的质因数列表
private
static
List<Integer> factorList =
new
ArrayList<Integer>();
// 这个availablePrimeFactorList用于存放所有不超过被分解的数的素数列表，他们中的每个将从小到大依次拿去尝试
private
static
List<Integer> availablePrimeFactorList;
/**
* 判断一个数是否是素数，判断的方法是用2,3,4..一直到 sqrt(number)的值去作为除数，
* 让number去除这些值，如果能整除，说明这个数不是素数
*
* @param number
* @return
*/
private
static
boolean
isPrime(
int
number) {
// 1不是素数
if
(number ==
1
)
return
false
;
// 判断一个数是否是素数，判断的方法是用2,3,4..一直到 sqrt(number)的值去作为除数，
// 让number去除这些值，如果能整除，说明这个数不是素数
for
(
int
i =
2
; i <= Math.sqrt(number); i++) {
if
(number % i ==
0
) {
return
false
;
}
}
return
true
;
}
/**
* 返回一个素数列表，其中的每一个素数都不超过被测的值
*
* @param number
* @return
*/
public
static
List<Integer> makeAvailablePrimeFactorList(
int
number) {
List<Integer> availablePrimeFactorList =
new
ArrayList<Integer>();
// 2是最小的素数，从2开始一直算到被测的数，如果此数为素数，则被添加到可用的素数列表中
for
(
int
i =
2
; i <= number; i++) {
if
(isPrime(i))
availablePrimeFactorList.add(i);
}
return
availablePrimeFactorList;
}
/**
* 分解质因数,这是一个递归调用
*
* @param number
*/
private
static
void
decomposite(
int
number) {
// 如果当前数已经是素数，那么分解到头了，吧当前的素数也作为质因子
if
(isPrime(number)) {
factorList.add(number);
return
;
}
// 如果当前可用素数列表中没有素数了，那么结束
if
(availablePrimeFactorList.size() ==
0
)
return
;
// 当前可用素数列表中的最小素数
int
currentPrime = availablePrimeFactorList.get(
0
);
// 如果number被当前素数整除，那么吧当前素数添加到factor列表中，更新待分解的数为 number/currentPrime
if
(number % currentPrime ==
0
) {
factorList.add(currentPrime);
decomposite(number / currentPrime);
}
// 如果number不可以被当前素数整除，那么从可用素数列表中移除当前的素数，从下一个素数开始
else
{
availablePrimeFactorList.remove(
0
);
decomposite(number);
}
}
/**
* @param args
*/
public
static
void
main(String[] args) {
// 被分解的数
int
number =
78
;
// 获得所有小于被分解的数的素数的列表
availablePrimeFactorList = makeAvailablePrimeFactorList(number);
// 分解质因数
decomposite(number);
// 打印出所有的质因子,这些质因子来自factorList
System.out.print(number +
"="
);
for
(
int
i =
0
; i < factorList.size(); i++) {
System.out.print(factorList.get(i));
if
(i < factorList.size() -
1
)
System.out.print(
"*"
);
}
}
}
|
比如，我这里测试78，那么显示：
本文转自 charles_wang888 51CTO博客，原文链接：http://blog.51cto.com/supercharles888/1345641，如需转载请自行联系原作者
