【因子算法】——求一个数的因子、质因子、求两个数的公因子

98 阅读 0 评论 65 点赞

我是靠谱客的博主激动猎豹，这篇文章主要介绍【因子算法】——求一个数的因子、质因子、求两个数的公因子，现在分享给大家，希望可以做个参考。

下面理清楚一些数学概念：

因数：一个数，如果存在可以被它整除的数，则这些数都是该数的因数。

规定0没有因数，1的因数是1，其他的比如4的因数有“1”、“2”、“4

因子：一个数，如果存在可以被它整除的数且这些数不包括它本身，则这些书都是该数的因子。

规定0没有因子，1的因子是1，其他的比如4的因子有“1”、“2”

质因子：一个数，如果可以分解成n个质数相乘，则n个质数成为该数的质因子。

规定0和1没有质因子，质数的质因子为其本身

完数：一个数的因子之和等于它本身，则该数为完数。

场景一：输入有一个自然数n，输出其所有的因子，并返回因子的个数（这里通常指的是正因子）。

思路：如果是0，则返回0；如果是1，则返回1，如果是2，则返回2；如果大于2，则从2到根号n依次判断取余即可

代码实现（java）

复制代码

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
	/**
* 求一个数的因子,这里值的是正因子，包含1，但不包含本身。
* @param n 自然数
* @return 因子的个数
*/
public static int getFactors(int n){
int count = 0;
if(n == 0)
return count;
else if(n == 1 || n == 2){
System.out.println("n");
return ++count;
}
else{
//包含1
System.out.print(1+" ");
int l = (int) Math.sqrt(n);
for(int i = 2; i <= l; i++){
if(n % i == 0){
System.out.print(i+" ");
System.out.print(n/i+" ");
count += 2;
}
}
}
return count+1;
}

场景二：输入有一个自然数n，输出其所有的质因子，并返回质因子的个数。

思路：如果是0或者1，则返回0；否则，则先判断是否为质数，如果不是，用一个cur变量保存“能被整除的质数”，先赋值为2.，依次从cur开始做取余操作，如果不为0则cur递增取下一个质数，直到余数为0，cur保存当前质数，n保存为n/cur,直到为质数为止。

代码实现（java）

复制代码

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
	/**
* 求一个自然数的质因子
* @param n 自然数
* @return 质因子个数
*/
public static int getFactorsByPrimeNumber(int n){
LinkedList<Integer> list = new LinkedList<Integer>();
list.add(2);
int m = n;
if(n == 0 || n ==1)
return 0;
else{
if(Day1.isPrimeNumber(m)){
list.add(n);
System.out.print(n+"= 1*"+n);
return 1;
}else{
int curLast = 0;
while(!Day1.isPrimeNumber(m)){
curLast = list.getLast();
while(true){
if(Day1.isPrimeNumber(curLast)){
if(m % curLast == 0){
list.add(curLast);
m = m / curLast;
break;
}
}
curLast++;
}
}
list.add(m);
//打印输出
int valuse = list.get(1);
int count = 1;
System.out.print(n+"="+valuse);
for(int i = 2; i < list.size(); i++){
System.out.print("*"+list.get(i));
if(valuse != list.get(i)){
count++;
valuse = list.get(i);
}
}
return count;
}
}
}

测试数据打印如下

复制代码

1
2
3
4
5
6
40=2*2*2*5
40的质因子一共有2个
96=2*2*2*2*2*3
96的质因子一共有2个
157= 1*157
157的质因子一共有1个

场景三：输入两个数n和m，输出n和m的公因子，并返回公因子个数，

思路：两个数的公因子包含必定是两个数的最大公约数的因子，如果最大公约数为n或者m，则公因子还包括最大公约数本身。

代码实现（java）

复制代码

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
/**
* 求两个数的公因子
* 思路：
* 1. 先求两个数的公约数
* 2. 对最大公约数进行求因子。如果该公约数为所求两个数较小的数，则公因子不包括该数，否则则包括
*
比如 30 15
最大公约数为15 公因子为 1 3 5
*
比如 20 8
最大公约数为4
公因子为 1 2 4
* @param n m 参数
* @return 公因子个数
*/
public static int getAllFactors(int n,int m){
int count = 0;
if(n ==0 || m ==0)
return 0;
else{
//调用最大公约数函数
int greatestCommonMeasure = Tools.getGreatestCommonMeasure_2(n, m);
if(greatestCommonMeasure == 0){
return greatestCommonMeasure;
}else if(greatestCommonMeasure == 1){
System.out.println(1+" ");
return greatestCommonMeasure;
}else{
System.out.print(1+" ");
count++;
if(greatestCommonMeasure != n && greatestCommonMeasure != m){
count++;
System.out.print(greatestCommonMeasure+" ");
}
int l = (int) Math.sqrt(greatestCommonMeasure);
for(int i = 2; i <= l; i++){
if(greatestCommonMeasure % i == 0){
System.out.print(i+" ");
System.out.print(greatestCommonMeasure/i+" ");
count += 2;
}
}
}
return count;
}
}