方法有很多（各有各的优点） 静下心看
第一种 穷举法
解释：如果两个数能够整除 则最大公因数是那个小的数 例如 20和5 20/5==4 则最大公因数为5
若不能整除 则最大公因数是 比小数小的（肯定是在小数上找） 且能被两个数整除的
int xxx(int a, int b) //定义找最大公因数的函数
{
int i;
int min = a < b ? a : b; //在小数上找
for (i = min; i >= 1; i--) //先从小数的最大值开始 因为是最大公因数
{
if (a % i == 0 && b % i == 0) //被两个数同时整除
}
return i; //返回i的值
}
第二种 质数分解法
将所有的公有小公因数相乘 就是 最大公因数
求 20和 40 的最大公因数。
先对 20 进行质因数分解：20=2*2*5再对 40进行质因数分解：40=2*2*2*5公有的质因数是 2 和 5，其中 2 出现两次，5 出现一次，所以最大公因数为2*2*5=20代码实现 还不能理解的可以带入是数据验证 这样好理解
int xxx(int a, int b) //定义函数
{
int result = 1; //定义一个存放结果的变量
for (int i = 2; i <= a && i <= b; i++) 也能从 1开始 不过从1开始的话结果不变 反而增加计算量
{
while (a % i == 0 && b % i == 0) //直到找到公因数
{
result *= i;
a /= i;
b /= i;
i = 1; //找到之后 又从1开始找
}
}
return result; //返回
}
第三种 辗转相除法
辗转相除法，又称欧几里得算法，其基本原理是：用较大数除以较小数得到商和余数，再用除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公因数。
// 函数用于求两个数的最大公因数，使用辗转相除法
int xxx(int a, int b) {
int temp;
while (b!= 0) {
temp = b;
b = a % b;
a = temp;
}
return a;
}
第四种 更相减损术
更相减损术的原理是：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，此时这个相等的数就是最大公因数。
// 函数用于求两个数的最大公因数，使用更相减损术
int xxx(int a, int b) {
while (a!= b) {
if (a > b) {
a = a - b;
} else {
b = b - a;
}
}
return a;
}