求最大公约数的辗转相除法,如何利用辗转相除法求最大公约数

更相减损法原理

假设有两个数161和63，我们要求这两个数的最大公因数，不妨假定这个最大公因数为m，我们可以将较大的数161看成63+98，63与98的和161可以被m整除，其中63也可以被m整除，自然98可以被m整除；

所以这个问题就转换为求98和63的最大公因数m（和上面m相等）
将98看成63+35，其中63可以被m整除，和98也能被m整除，故35也可以被m整除；

所以问题进一步转换为求35和63的最大公因数m（和上面m相等）
同理转换为求 (63-35)=>28和35 的最大公因数然后转换为求28和7的最大公因数…（一直减呀减）

后来转换为求7和7的最大公因数
最后转换为求7和0的最大公因数
输出第一个数字即可；这就是相减损术的原理

#include<stdio.h> main(){int a,b,num1,num2;printf("请输入这两个数：");scanf("%d %d",&a,&b);num1=a,num2=b;while(a!=b)/* a, b不相等，大数减小数，直到相等为止。*/ {if(a>b)a-=b;elseb-=a;}//a==b结束循环，根据更相减损术，若a==b,则a（或b）即为两数的最大公约数。printf("a、b的最大公约数为:%dn",a);printf("a、b的最小公倍数为:%d",num1*num2/a);//最小公倍数=两整数的乘积÷最大公约数} 辗转相除法原理

辗转相除法是求最大公约数的一种方法。它的具体做法是：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

int gcd(int a,int b){if(b==0) return a;else return gcd(b,a%b);}

或者更加简洁的写法有

int gcd(int a,int b){return !b?a:gcd(b,a%b);}