c语言练习77：公因⼦的数⽬

公因⼦的数⽬

题⽬描述：

给你两个正整数 a 和 b ，返回 a 和 b 的公因⼦的数⽬。

如果 x 可以同时整除 a 和 b ，则认为 x 是 a 和 b 的⼀个公因⼦ 。

• ⽰例 1：

输⼊：a = 12, b = 6

输出：4

解释：12 和 6 的公因⼦是 1、2、3、6 。

• ⽰例 2：

输⼊：a = 25, b = 30

输出：2

解释：25 和 30 的公因⼦是 1、5 。

算法思路：

1. 定义⼀个变量 m ⽤来记录 a 和 b 的最⼩值；

2. 定义⼀个变量cnt，将其初始化为0；

3. 以 m 为上限，1为下限遍历整数，若当前数同时整除 a 和 b ，则 cnt 的值加⼀；

4. 返回 cnt 。

int commonFactors(int a, int b) {
	//定义变量记录最⼩值
	int m = (a > b ? a : b);
	//定义变量记录公因⼦个数
	int cnt = 0;
	//从m开始，从⼤到⼩遍历整数
	while (m >= 1) {
		//判断当前数是否同时整除a和b
		if (a % m == 0 && b % m == 0) {
			//若同时整除则记录个数
			cnt++;
		}
		//当前数处理完成，遍历下⼀个数
		m--;
	}
	//返回公因⼦个数
	return cnt;
}

解法⼆（数学优化）： a 和 b 所有的公因⼦都可以作为 a 和 b 的最⼤公因数的因⼦，反之， a 和 b 的最⼤公因数的所 有因⼦都可以作为 a 和 b 的公因⼦。所以，我们只需要求得 a 和 b 的最⼤公因数的因⼦数就可以 得出 a 和 b 的公因⼦数。

假设 x 是 n 的⼀个因⼦，则 x 可以整除 n 。则 n/x 是⼀个整数，并且 x*(n/x) 的结果是 n ， 则 n/x 也是n的⼀个因⼦。 

• 这⾥，假设 x*y=n ， x=z ，当且仅当x=y=z时等 号成⽴。

反证法： 当 x=y=z 时， x*y=z*z=n ， 如果 xz，y>=z ，则 x*y>n ⼀定成⽴， 则 x=z 若不能同时成⽴， {x,y} 数对不存在，得证。

因此，我们只需要遍历可能成⽴的 x 即可找到相应的 y ，需要注意的是当 x=y 时的情况。

算法思路：

1. 定义⼀个变量 m 记录a和b的最⼤公约数；

2. 定义⼀个变量 cnt ，将其初始化为0，⽤来记录公因⼦个数；

3. 以1为下限，m的开⽅为上限，遍历每个整数 i ；

4. 若 i 是 m 的因⼦， cnt 的值加⼀；

5. 若m/i与i不相等， cnt 的值加⼀；

6. 返回 cnt 。

//定义函数计算最⼤公约数
int gcd(int a,int b){
	return b == 0 ? a : gcd(b, a % b);
 }
int commonFactors(int a, int b) {
	//记m为a和b的最⼤公约数
	int m = gcd(a, b);
	//记录a和b的公因⼦
	int i = 0;
	int cnt = 0;
	//以最⼤公约数的开⽅为上限，从1开始遍历，当i≤m的开⽅时，i*i≤m
	for (i = 0; i * i <= m; i++) {
		if (m % i == 0) {
			//x是m的因⼦，可以作为a和b的公因⼦
			cnt++;
			//如果i*i!=m，则m/i（不与i相等）也可以作为m的因⼦，即a和b的公因⼦
			if (i * i != m) {
				cnt++;
			}
		}
	}
	//返回公因⼦个数
	return cnt;
}