短除法求解最大公约数c语言 [编程入门]最大公约数与最小公倍数-题解（C语言代码）(短

解题思路:

很多人都用辗转相除法来递归，但是我们上中学时用的更多的应该是短除法，或者叫倒除法，我们进行进制转换时也会用到这种方法

所以我想利用短除法写出代码来表示，也是给大家提供一种不同的思考方式

那么什么是短除法：

假设我们输入 m=12，n=18 ，初始化最大公约数 gcd=1

我们发现 2 是12和18的一个公因子

我们令 m /= 2 ，n /= 2 ，gcd *= 2

现在 m == 6 , n == 9 , gcd == 2

又发现 3 是 6 和 9 的一个公因子

我们令 m /= 3 , n /= 3 , gcd *= 3

现在m == 2 , n == 3 , gcd == 6

我们找不到除 1 以外的 2 和 3 的公因子了

所以现在的 gcd == 6 就是我们要找的最大公因数

而最小公倍数 lcm = gcd * m * n = 6 * 2 * 3 = 36

图片：

参考代码:#include

intmain()

{

intm,n;

intj,k;

intlcm,gcd=1;

scanf("%d%d",&m,&n);//输入m和n

j=m,k=n;//用j和k表示m和n，不破坏m与n的值

if(j>k)

{

j=n,k=m;//确保j是较小的那个

}

for(inti=2;i<=j;i++)//循环寻找从i到j的因子(注意j是可变的，而i会被重置)

{

if(j%i==0&&k%i==0)//判断i是否为j和k的公因子

{

j/=i;

k/=i;//j与k分别除以i

gcd*=i;//gcd乘以i

i=1;//将i重置为1(循环末尾会i++)

}

}

lcm=gcd*j*k;//求出最小公倍数lcm

printf("%d%d",gcd,lcm);//输出gcd与lcm

return0;

}

短除法求解最大公约数c语言 [编程入门]最大公约数与最小公倍数-题解（C语言代码）(短除法)...