C语言之求最大公约数

发布网友发布时间：2022-04-24 12:03

共2个回答

热心网友时间：2022-05-07 04:28

这个函数是用的辗转相除法来求最大公约数；

用（a,b）来表示a和b的最大公约数。
有定理：已知a,b,c为正整数，若a除以b余c，则（a,b）=(b,c)。（证明过程请参考其它资料）例

：求 15750 与27216的最大公约数。
   解：
∵27216=15750×1+11466 ∴（15750，27216）=（15750，11466）
∵15750=11466×1+4284 ∴（15750，11466）=(11466,4284)
∵11466=4284×2+2898 ∴(11466,4284)=（4284，2898）
∵4284=2898×1+1386   ∴（4284，2898）=（2898，1386）
∵2898=1386×2+126   ∴（2898，1386）=（1386，126）
∵1386=126×11     ∴（1386，126）=126

   所以（15750，27216）=216

也就是说不断用较大的数除以较小的数（再将较小的数作为大数；将余数作为小数）直到余数为0

热心网友时间：2022-05-07 05:46

解释如下：
int f(int m,int n)
{
int r;
if(m<m) //如小数除以大数，就交换一下
{
r=m;m=n;n=r;
}
r=m%n; //取大数除以小数的余数
while(r) //当余数不为0时进入循环
{
m=n;n=r;r=m%n; //让上一轮的除数作为新的被除数，上一轮的余数作为新的除数，取新的余数
}
return n; //以余数为0时的除数，作为最大公约数返回
}